Codeforces Round 888 (Div. 3) |
---|
Закончено |
Влад решил отправиться в путешествие в горы. Всего он планирует перемещаться по $$$n$$$ горам, между некоторыми из которых есть дороги. Горы имеют высоты, высота $$$i$$$-й горы равна $$$h_i$$$.
Если между горами $$$i$$$ и $$$j$$$ есть дорога, то Влад может перейти с горы $$$i$$$ на гору $$$j$$$, потратив при этом $$$h_j - h_i$$$ единиц энергии. Если при переходе его энергия должна опуститься ниже нуля, он не сможет перейти с горы $$$i$$$ на гору $$$j$$$. Обратите внимание, что $$$h_j - h_i$$$ может быть отрицательным и тогда энергия восстановится.
Влад хочет рассмотреть разные варианты маршрута, поэтому просит вас ответить на следующие запросы: можно ли построить какой-либо маршрут, начинающийся на горе $$$a$$$ и заканчивающийся на горе $$$b$$$, если изначально у него есть $$$e$$$ единиц энергии?
В первой строке входных данных содержится целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.
Далее следуют описания наборов.
Первая строка набора содержит два числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le \min(\frac{n\cdot(n - 1)}{2}, 2 \cdot 10^5)$$$) — количество гор и дорог между ними, соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$h_1, h_2, h_3, \dots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — высоты гор.
Следующие $$$m$$$ строк содержат по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — номера гор, которые соединяет дорога. Гарантируется, что ни одна дорога не встречается дважды.
Следующая строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.
Следующие $$$q$$$ строк содержат по три числа $$$a$$$, $$$b$$$ и $$$e$$$ ($$$1 \le a, b \le n$$$, $$$0 \le e \le 10^9$$$) — начальная и конечная горы маршрута и количество энергии, соответственно.
Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$. Также это гарантируется для $$$m$$$ и $$$q$$$.
Для каждого запроса выведите «YES», если Влад может составить маршрут от горы $$$a$$$ до горы $$$b$$$, и «NO» в противном случае.
Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
В примерах ниже ответы на разные наборы данных разделены пустой строкой, вы можете её не выводить.
27 71 5 3 4 2 4 11 44 33 63 22 55 65 751 1 36 2 04 7 01 7 41 7 26 54 7 6 2 5 11 35 31 52 46 251 5 11 3 11 2 10006 2 66 2 5
YES NO YES YES NO YES NO NO YES NO
23 21 3 91 22 351 1 13 2 21 1 23 3 01 2 13 31 4 11 22 31 353 3 91 3 61 1 23 3 63 3 4
YES YES YES YES NO YES YES YES YES YES
16 107 9 2 10 8 64 26 14 53 56 41 32 66 51 23 654 4 83 3 15 5 92 1 76 6 10
YES YES YES YES YES
Название |
---|