Informatica Online Judge

  도시감염 [1934 / 078E]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 3   Total Tried : 4


The Champion of this Problem (C++) : icp1481 - 280ms / 1221byte
My Best Submission (C++) : N/A

[koistudy.net (34th 남동준)]
Writer ID : [gs16028]

Background

0부터 N-1개의 번호가 주어진 N개의 도시가 있는 GSHS국이 있다.

각 도시는 간선으로 연결되어 있고, 연결되지 않은 도시로는 갈 수 없다.

지난 정보과학에서 C+를 받은 경곽이는 특제 좀비 바이러스를 이용하여
GSHS국을 전부 감염시키려 한다.

이 특제 좀비 바이러스는 다음과 같은 성질을 가지고 있다.

- 감염된 도시와 인접해 있는 건강한 도시와 감염된 도시 모두 매 시간당 체력이 1씩 감소한다.
(감염된 도시의 체력이 감소하는 것을 우선적으로 계산한다.)

- 건강한 도시가 체력이 0이 되면, 처음 체력을 가진 감염된 도시로 부활한다.

- 감염된 도시가 체력이 0이 되면, 죽은 도시가 된다.(죽은 도시는 없는 도시 취급한다.)

경곽이는 한 개의 초기 도시를 잡아 그 도시를 완전히 감염된 상태로 시작할 수 있다.

여러개의 쿼리에 대해서 초기 도시가 정해져 있을때, 오랜 시간이 지나도 건강한 도시가 남아있을 수 있는지 구해보자.

Input

첫 줄에 정수 N, M(N < 100)이 주어진다.

이후 N개의 줄에 각 도시의 체력(0 < a[i] <= 10000)이 주어진다.

이후 M개의 줄에 간선의 정보가 두 정수 a,b(1 <= a < b <= n)로 주어진다.

각 도시 사이의 간선은 최대 1개이며, 양방향으로 이동할 수 있다.

이후 쿼리의 개수 Q(Q<=20)가 주어진다.

이후 Q개의 줄에 초기 도시의 숫자k(0 <= k < n)가 주어진다.

Output

오랜 시간이 지나도 건강한 도시가 남아있을 수 있는지 여부를 출력한다.
남아있을 수 있으면 Survive, 아니면 Dead를 출력한다.

IO Example

입력
3 3
4
5
7
0 1
1 2
0 2
3
0
1
2

출력
Survive
Dead
Dead

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]