Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Всем известно о существовании вампиров. Однако, никто не задумывается о непосредственной близости этих существ.
В сумеречном королевстве имеется `n` городов. Между некоторыми городами есть двусторонние дороги.
В каждом городе есть свой вампирский клан, в который входит `k_i` вампиров.
В свое время вампиры изгнали из королевства всех оборотней, сделав их тем самым своими лютыми врагами.
Оборотням это, естественно, не понравилось. Они решили объединиться в один отряд и напасть на какой-нибудь город.
Отряд, нападающий на город, содержит `w` оборотней.
Однако, приняв в рассчет то, что вампиры всегда действуют сообща, оборотни начали сомневаться в успешности их нападения.
Теперь они пришли к вам за помощью. Известно, что вампиры могут перемещаться между двумя городами, соединенными дорогой,
за один день. Также известно,
что за один день сражения погибает `min(t,\ a,\ b)` вампиров, обороняющих осажденный город, и столько же оборотней,
где `a` – текущая численность отряда вампиров,
`b` – текущая численность отряда оборотней, `t` – константа. По данной вам информации,
требуется узнать, смогут ли вампиры защитить город.
Город считается осажденным, если существует момент времени, когда число оборотней, напавших на город, больше нуля, а число
вампиров, обороняющих город, равно нулю.
В самой первой строке написано три числа: `n` (`1\ ≤\ n\ ≤\ 10^5`) – количество городов,
`m` (`1\ ≤\ m\ ≤\ 10^5`) – количество дорог,
`t` (`1\ ≤\ t\ ≤\ 10^3`) – количество вампиров и оборотней, погибающих за один день сражения.
Во второй строке написано ровно `n` чисел: `k_i` (`1\ ≤\ k_i\ ≤\ 10^4`) – количество вампиров в `i`-м городе.
Следующие `m` строк описывают дороги между городами: в каждой строке написано два числа – номера городов, соединенных дорогой.
В последней строке написан номер города, на который было произведено нападение, и `w` (`1\ ≤\ w\ ≤\ 10^4`) –
размер армии оборотней.
Выведите "Vampires win", если вампиры смогут отстоять свой город, и "Werewolves win" иначе.
Пример ввода 1
5 6 5
4 5 4 4 1
1 5
1 3
2 1
3 5
2 5
4 3
1 8
Пример вывода 1
Werewolves win
Пример ввода 2
5 5 1
3 1 5 1 1
1 2
1 5
1 4
4 5
2 3
1 11
Пример вывода 2
Vampires win
Обратите внимание, что в случае, если в городе погибают все вампиры, а новый отряд из соседнего города приходит на следующий день,
вампиры все равно проигрывают.
Источник: neerc.ifmo.ru/school