---> 16 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 3 4 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В этой задаче Вам вновь придется помочь Берляндии. Эта страна состоит из $n$ городов, некоторые пары из которых соединены двусторонними дорогами, каждая дорога характеризуется своей длиной. Все города пронумерованы числами от 1 до $n$, столица имеет номер 1. Время от време ни Президент объезжает страну, посещая города страны. Целью каждой поездки является один из городов, к которому он едет из столицы вдоль дорог одним из кратчайших путей.

В далекие времена (когда задачи на алгоритм Дейкстры вызывали сложность) специальное ведомство составила такой набор дорог $T$, вдоль которого можно было проехать из столицы в любой город, причем единственным образом. Разумеется, путь по дорогам из набора $T$ из столицы в каждый город являлся кратчайшим. Особо умные жители страны попросту называли этот набор дорог "деревом кратчайших путей". Известно, что Президент пользовался дорогами из $T$ во время своих поездок. За прошедшие годы этот набор перестал быть секретным, и, поэтому, стал объектом повышенного внимания берляндских экстремистов. У специального ведомства новое задание. Для каждого города кроме столицы необходимо вычислить кратчайшее расстояние до него, при условии, что та дорога по которой Президент должен был закончить свой путь в этот город является атакованной и проезжать по ней нельзя.

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

В первой строке входного файла записана пара целых чисел $n$ и $m$ ($2 \leq n \leq 4\,000$; $ n - 1 \leq m \leq 100\,000$), где $n$ — количество городов в стране, а $m$— количество дорог в этой стране. Далее в $m$ строках содержатся описания дорог, по одной дороге в строке. Каждая дорога задается четверкой целых чисел $a_j$, $b_j$, $l_j$, $t_j$ , где $a_j$, $b_j$ это номера городов, соединяемых дорогой ($1 \leq a_j, b_j \leq n$; $a_j \neq b_j$), $l_j$ — ее длина ($1 \leq l_j \leq 10^5$), а $t_j$ равно 1 если дорога принадлежит дереву кратчайших путей и 0 в противном случае.

Гарантируется, что набор $T$ удовлетворяет описанным выше свойствам. Между парой городов может быть более одной дороги. Все дороги двусторонние.

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

Выведите $n - 1$ число в строку через пробелы. $i$-ое число должно быть равно либо длине кратчайшго пути из столицы в город $i + 1$, при условии, что по той дороге из $T$, которой Президент заканчивал свой путь в этот город, передвигаться нельзя, либо -1, если добраться до города $i + 1$ вообще невозможно.

Примеры
Входные данные
5 9
3 1 3 1
1 4 2 1
2 1 6 0
2 3 4 0
5 2 3 0
3 2 2 1
5 3 1 1
3 5 2 0
4 5 4 0
Выходные данные
6 7 8 5

Постановка задачи о {Наименьшем общем предке} такова: дано дерево T с выделенным корнем и две вершины u и v, lca(u, v) - вершина с максимальной глубиной, которая является предком и u, и v. Например, в картинке внизу lca(8, 7) - вершина 3.

С помощью операции chroot(u) мы можем менять корень дерева, достаточно отметить u, как новый корень, и направить ребра вдоль пути от корня. Наименьшие общие предки вершин поменяются соответствующе. Например, если мы сделаем chroot(6) на картинке сверху, lca(8, 7) станет вершина 6. Получившееся дерево изображено снизу.

Вам дано дерево T. Изначально корень этого дерева - вершина 1. Напишите программу, которая поддерживает эти две операции: lca(u, v) и chroot(u).

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

Входной файл состоит из нескольких тестов.

Первая строка каждого теста содержит натуральное число n  — количество вершин в дереве (1 ≤ n ≤ 100 000). Следующие n - 1 строки содержат по 2 натуральных числа и описывают ребра дерева. Далее идет строка с единственным натуральным числом m — число операций —. Следующие m строк содержат операции. Строка "? u v" означает операцию lca(u, v), a строка "! u" - chroot(u). Последняя строка содержит число 0.

Сумма n для всех тестов не превосходит 100 000. Сумма m для всех тестов не превосходит 200 000.

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

Для каждой операции "? u v" выведите значение lca(u, v). Числа разделяйте переводами строк.

Система оценки:

Система тестов состоит из двух групп:

Первая группа состоит из тестов, для которых выполняется ограничение $n \le 100$, $m \le 10000$. За прохождение всех тестов группы ставится 55 баллов.

Вторая группа стоит из тестов, в которых нет дополнительных ограничений. За прохождение тестов этой группы и всех предыдущих тестов ставится дополнительно 45 баллов.

Примеры
Входные данные
9
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
10
? 4 5
? 5 6
? 8 7
! 6
? 8 7
? 4 5
? 4 7
? 5 9
! 2
? 4 3
0
Выходные данные
2
1
3
6
2
3
6
2
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Задано подвешенное дерево, содержащее n (1 ≤ n ≤ 100000) вершин, пронумерованных от 0 до n - 1. Требуется ответить на m (1 ≤ m ≤ 100000) запросов о наименьшем общем предке для пары вершин.

Запросы генерируются следующим образом. Заданы числа a1, a2 и числа x, y и z. Числа a3, ..., a2m генерируются следующим образом: ai = (x·ai - 2 + y·ai - 1 + z)mod: n. Первый запрос имеет вид (a1, a2). Если ответ на (i - 1)-й запрос равен v, то i-й запрос имеет вид ((a2i - 1 + v)mod: n, a2i).

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

Первая строка содержит два числа: n и m. Корень дерева имеет номер 0. Вторая строка содержит n - 1 целых чисел, i-е из этих чисел равно номеру родителя вершины i. Третья строка содержит число содержит два целых числа в диапазоне от 0 до n - 1: a1 и a2. Четвертая строка содержит три целых числа: x, y и z, эти числа неотрицательны и не превосходят 109.

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

Выведите в выходной файл сумму номеров вершин — ответов на все запросы.

Примеры
Входные данные
3 2
0 1
2 1
1 1 0
Выходные данные
2
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Чип и Дейл спешат на помощь! Но внимательные зрители знают, что помощь как правило нужна самим Чипу и Дейлу, поэтому сегодня вам надо будет сыграть роль сообразительной Гаечки. Итак, Чип и Дейл снова попали в лапы к Толстопузу. Кот очень не любит грызунов и поэтому приготовил им изощренное испытание. Он собирается поместить их в лабиринт и посмотреть смогут ли они из него выбраться. Лабиринт представляет собой дерево, в котором каждое ребро имеет одно направление. Гаечка подслушала разговор Толстопузу со своими сообщниками и теперь знает несколько возможных вариантов: в какую точку лабиринта поместят её друзей, и где будет выход. Для каждого такого варианта она хочет понять, смогут ли Чип и Дейл найти выход, или нет.

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

В первой строке записано число $n$ ($n \leq 10^5$) - количество вершин дерева. В следующих $n-1$ строках описаны ребра дерева. В $i+1$-ой строке записано номера вершин $a_i, b_i$, означающие, что в дереве есть ребро из вершины $a_i$ в вершину $b_i$.

Далее на отдельной строке записано число $m$ ($m \leq 10^5$) -- количество запросов. После этого идут $m$ строк с описанием запросов, в $n + 1 + i$-ой строке записаны через пробел числа $x_i$ и $y_i$.

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

Для каждого запроса на отдельной строке требуется вывести Yes, если в графе есть путь между вершинами $x_i$ и $y_i$, и No иначе.

input.txtoutput.txt
4
1 2
3 1
4 1
6
1 2
3 2
2 3
4 2
4 3
2 1
Yes
Yes
No
Yes
No
No
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Как известно, автобус должен ходить по расписанию. И Иннокентий, используя свои многочисленные связи в магазине плитки, совершил невозможное: по маршруту теперь курсируют целых $M$ автобусов, и на каждой остановке висит свое расписание, которое представляет собой набор из $M$ времен. Плиточный магнат является крупным авторитетом в городе, поэтому расписание соблюдается: от каждой остановки ровно в каждое из указанных времен отправляется автобус. Казалось, что проблема общественного транспорта навсегда решена...

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

Иннокентий решил оценить масштабы трагедии. Для этого он попросил каждого из Q своих друзей сообщить маршрут, по которому они добираются до места работы. Каждый маршрут описывается тремя числами $u_i$, $v_i$, $w_i$: $u_i$ — это номер остановки, ближайшей к дому i-го друга, $v_i$ — номер остановки, ближайшей к его работе, а $w_i$ — номер автобуса,на котором i-й друг едет из дома на работу. При этом с точки зрения i-го друга автобусы нумеруются от $1$ до $M$ в том порядке, в котором они отправляются с остановки $u_i$.

Иннокентий просит вас независимо для каждого друга определить, насколько поздно тот может доехать до конечной остановки своего маршрута.

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

В первой строке входных данных содержатся два целых числа $N$ и $M$ — количество остановок и количество автобусов соответственно ($2 \le N * M \le 150 000$). В следующей строке содержатся $N-1$ целых чисел $travel_1$, . . . , $travel_{N-1}$, где $travel_i$ — минимальное время, необходимое для перемещения между остановками i и i + 1 ($1 \le travel_i \le 10^9$).

В следующих $N$ строках содержатся описания расписаний, каждое из которых представляет собой отсортированный по возрастанию список из $M$ различных целых чисел $t_i$ — времен, в которые автобусы должны отправляться с соответствующей остановки ($1 \le t_i \le 10^9$).

В следующей строке содержится число T — тип теста (1 или 2). Если T = 1, то это — обычный тест. Тогда на следующей строке содержится целое число Q — количество опрошенных друзей Иннокентия ($1 \le Q \le 150 000 $). Далее в Q строках содержатся описания маршрутов друзей, каждое из которых состоит из трех целых чисел $u_i$, $v_i$ и $w_i$: номеров остановок, где начинается и заканчивается поездка i-го друга, и номер автобуса в расписании остановки ui, на котором эта поездка совершается ($1 \le u_i < v_i \le N, 1 \le w_i \le M$).

\textbf{Обратите внимание} : дальнейшее описание относится только к последней группе тестов. Если T = 2, то это — тест-серия. Тогда на следующей строке содержатся три целых числа — A, B и K ($1 \le A, B \le 10^3 , 1 \le K \le 150$).

В \t{тесте-серии} у Иннокентия Q = (N -1)·M ·K друзей. На каждой из N - 1 остановок, кроме последней, проживает ровно M * K друзей, причем для каждого $w$ от 1 до M есть ровно K друзей, которые уезжают с этой остановки w-м автобусом.

Остановки, до которых едут K друзей, уезжающих с u-й остановки w-м автобусом, определяются следующим образом. Задается последовательность чисел $q_i$: $q_1$ = A, $q_2$ = B, для i > 2 $q_i$ = u * $q_{i-1}$ + w * $q_{i-2}$ + 42. Тогда i-й из этих K друзей будет ехать до остановки с номером $v_i$ = u + 1 + ($q_i$ mod (N - u)), где mod обозначает операцию взятия остатка от деления.

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

Если это обычный тест, то выведите для каждого друга в отдельной строке единственное целое число - искомое максимальное время прибытия на конечную остановку в его маршруте. Если это тест-серия, то выведите единственное целое число — остаток от деления суммы максимальных времен прибытия для всех друзей Иннокентия на $2^{32}$.

Примечание

Приведем пояснение ко второму тесту из условия.

Это \textbf{тест-серия}. В нем у Иннокентия 5 · 4 · 2 = 40 друзей. Например, с первой остановки вторым автобусом уезжают ровно пять друзей. Поясним, как в этом тесте для них определить конечные остановки. u = 1, w = 2. Строим последовательность $q_i$: $q_1$ = 9, $q_2$ = 10, $q_3$ = 1 · 10 + 2 · 9 + 42 = 70, $q_4$ = 1 · 70 + 2 · 10 + 42 = 132, $q_5$ = 1 · 132 + 2 · 70 + 42 = 314. По ней восстанавливаются конечные остановки для этих пяти друзей Иннокентия: $v_1$ = 1 + 1 + (9 mod 4) = 3, $v_2$ = 1 + 1 + (10 mod 4) = 4, $v_3$ = 1 + 1 + (70 mod 4) = 4, $v_4$ = 1 + 1 + (132 mod 4) = 2, $v_5$ = 1 + 1 + (314 mod 4) = 4.

Система оценки

Тесты к этой задаче состоят из шести групп. Каждая группа, кроме нулевой, оценивается в 20 баллов. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов \textbf{предыдущих групп}, исключая тесты из условия. В группах тестов с первой по четвертую включительно вам предлагаются только обычные тесты.

0. Тесты 1—2. Тесты из условия, оцениваются в ноль баллов.

1. Тесты 3—12. В тестах этой группы $N = 2, M \le 1 000, Q \le 1 000$.

2. Тесты 13—22. В тестах этой группы $N = 2, M \le 75 000, Q \le 75 000$.

3. Тесты 23—37. В тестах этой группы $N * M \le 150 000, N * Q \le 150 000$.

4. В тестах этой группы $N * M \le 150 000, Q \le 150 000$.

5. В этой группе вам предлагаются только тесты-серии. Другие дополнительные ограничения отсутствуют.

Примеры
Входные данные
2 3
1
1 10 21
11 21 31
1
3
1 2 1
1 2 2
1 2 3
Выходные данные
21
21
31
Входные данные
5 2
2 5 3 4
1 3
3 5
10 11
13 14
18 23
2
9 10 5
Выходные данные
667

Страница: 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест