아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Нападение

시간 제한2초메모리 제한1024 MB

요약
인접 도시의 뱀파이어가 하루에 한 간선씩 이동해 공격받은 도시를 지원할 때, 지원이 도착하기 전에 늑대인간이 방어군을 전멸시킬 수 있는지 판정한다.
난이도

보통10점 중 7점

유형
그래프, BFS, 최단 경로, 시뮬레이션
정답자
아직 제출이 없습니다

문제

Всем известно о существовании вампиров. Однако, никто не задумывается о непосредственной близости этих существ. В сумеречном королевстве имеется nn городов. Между некоторыми городами есть двусторонние дороги. В каждом городе есть свой вампирский клан, в который входит k_ik\_i вампиров.

В свое время вампиры изгнали из королевства всех оборотней, сделав их тем самым своими лютыми врагами. Оборотням это, естественно, не понравилось. Они решили объединиться в один отряд и напасть на какой-нибудь город. Отряд, нападающий на город, содержит ww оборотней.

Однако, приняв в рассчет то, что вампиры всегда действуют сообща, оборотни начали сомневаться в успешности их нападения. Теперь они пришли к вам за помощью. Известно, что вампиры могут перемещаться между двумя городами, соединенными дорогой, за один день. Также известно, что за один день сражения погибает min(t,a,b)min(t, a, b) вампиров, обороняющих осажденный город, и столько же оборотней, где aa --- текущая численность отряда вампиров, bb --- текущая численность отряда оборотней, tt --- константа. По данной вам информации, требуется узнать, смогут ли вампиры защитить город. Город считается осажденным, если существует момент времени, когда число оборотней, напавших на город, больше нуля, а число вампиров, обороняющих город, равно нулю.

입력

В самой первой строке написано три числа: nn (1≤n≤1051 \le n \le 10^5) --- количество городов, mm (1≤m≤1051 \le m \le 10^5) --- количество дорог, tt (1≤t≤1031 \le t \le 10^3) --- количество вампиров и оборотней, погибающих за один день сражения. Во второй строке написано ровно nn чисел: k_ik\_i (1≤k_i≤1041 \le k\_i \le 10^4) --- количество вампиров в ii-м городе. Следующие mm строк описывают дороги между городами: в каждой строке написано два числа --- номера городов, соединенных дорогой. В последней строке написан номер города, на который было произведено нападение, и ww (1≤w≤1041 \le w \le 10^4) --- размер армии оборотней.

출력

Выведите <<Vampires win>>, если вампиры смогут отстоять свой город, и <<Werewolves win>> иначе.

힌트

Обратите внимание, что в случае, если в городе погибают все вампиры, а новый отряд из соседнего города приходит на следующий день, вампиры все равно проигрывают.

예제2

  1. 예제 1

    입력
    5 6 5
    4 5 4 4 1
    1 5
    1 3
    2 1
    3 5
    2 5
    4 3
    1 8
    
    예상 출력
    Werewolves win
    
  2. 예제 2

    입력
    5 5 1
    3 1 5 1 1
    1 2
    1 5
    1 4
    4 5
    2 3
    1 11
    
    예상 출력
    Vampires win