Перевал Талдык


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.5s
Ограничение по памяти: 512M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Памирский тракт ведёт из Оша через перевал Талдык (3615 м) в Сары-Таш и дальше в горы. Вокруг тракта — n горных сёл, пронумерованных от 1 до n; село i расположено на высоте h[i] метров. Сёла соединены m дорогами с двусторонним движением. Дорога j соединяет сёла a[j] и b[j], а её мосты выдерживают грузовики массой не более w[j] тонн.

Логистическая компания «Ош-Транс» получает заявки от метеорологов: грузовик массой W тонн стоит в селе v и везёт оборудование для метеостанции. Станцию нужно поставить в одном из сёл, куда грузовик может доехать (по дорогам, которые его выдерживают; можно и остаться в селе v). Метеорологи хотят, чтобы станция стояла как можно выше, но самое высокое село часто уже занято, поэтому в заявке указано число k: нужно найти k-ю по величине высоту среди всех достижимых сёл (если несколько сёл расположены на одной высоте, каждое учитывается отдельно). Если достижимых сёл меньше k, ответ -1.

Заявки поступают по рации, и диспетчер узнаёт следующую заявку, только ответив на предыдущую. Поэтому заявки во входных данных зашифрованы: вместо чисел v, W, k даны числа x, y, z, и

v = x xor L, W = y xor L, k = z xor L,

где xor — побитовое исключающее ИЛИ, а L — ответ на предыдущую заявку (для первой заявки и после ответа -1 полагается L = 0).

Рисунок

Входные данные

В первой строке — два целых числа n и m (1 ≤ n ≤ 200 000, 0 ≤ m ≤ 400 000).

Во второй строке — n целых чисел h[1], …, h[n] (1 ≤ h[i] ≤ 10⁹).

В каждой из следующих m строк — три целых числа a[j], b[j], w[j] (1 ≤ a[j], b[j] ≤ n, a[j] ≠ b[j], 1 ≤ w[j] ≤ 10⁹). Между двумя сёлами может быть несколько дорог.

Далее — число q (1 ≤ q ≤ 200 000) и q строк, в каждой три целых числа x, y, z — зашифрованная заявка. Гарантируется, что после расшифровки 1 ≤ v ≤ n, 1 ≤ W ≤ 10⁹ + 1, 1 ≤ k ≤ n.

Выходные данные

Для каждой заявки выведите в отдельной строке k-ю по величине высоту среди сёл, достижимых из v грузовиком массой W, или -1.

Пример 1

Вход:

6 6
1500 3200 2800 4100 900 3600
1 2 4
2 3 2
3 4 5
2 4 3
5 6 7
4 6 1
6
2 3 1
4103 4097 4102
2806 2801 2803
3201 3205 3201
1497 1499 1503
5 8 1

Выход:

4100
2800
3200
1500
-1
900

Пояснение

Расшифрованные заявки: (2, 3, 1), (3, 5, 2), (6, 1, 3), (1, 5, 1), (5, 7, 3), (5, 8, 1).

Грузовик массой 3 тонны из села 2 может проехать по дорогам 1–2, 3–4, 2–4 и 5–6, то есть добраться до сёл 1, 2, 3, 4; самое высокое из них — село 4 (4100 м). Грузовик массой 7 тонн из села 5 доберётся только до сёл 5 и 6, третьего села нет, поэтому ответ -1, и следующая заявка не зашифрована (L = 0).

Система оценивания

Подзадача Баллы Дополнительные ограничения
1 20 n, m, q ≤ 2000
2 30 во всех заявках k = 1
3 50 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.


Комментарии

Еще нет ни одного комментария.