Страница: 1 2 3 4 >> Отображать по:

#724

Берляндия атакует

Темы: [Наименьший общий предок] [Дерево отрезков, RSQ, RMQ] [Разреженные таблицы (sparse table)]

В этой задаче Вам вновь придется помочь Берляндии. Эта страна состоит из $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$ вообще невозможно.

Примеры

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

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

6 7 8 5

#111711

Dynamic LCA

Темы: [Деревья] [Наименьший общий предок]

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

$\text{[math]}$

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

$\text{[math]}$

Вам дано дерево 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 баллов.

Примеры

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

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

#111796

LCA

Темы: [Деревья] [Наименьший общий предок]

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

Запросы генерируются следующим образом. Заданы числа a₁, a₂ и числа x, y и z. Числа a₃, ..., a_2m генерируются следующим образом: a_i = (x·a_i - 2 + y·a_i - 1 + z)mod: n. Первый запрос имеет вид (a₁, a₂). Если ответ на (i - 1)-й запрос равен v, то i-й запрос имеет вид ((a_2i - 1 + v)mod: n, a_2i).

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

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

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

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

Примеры

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

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

#111894

Чип и Дейл в лабиринте

Темы: [Наименьший общий предок]

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

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

В первой строке записано число $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.txt	output.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

#112034

Транспортные потоки

Темы: [Задачи на моделирование] [Дерево отрезков, RSQ, RMQ] [Обход в глубину] [Двоичные подъемы]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2012-2013, Заключительный этап - второй тур, Задача C ]

Как известно, автобус должен ходить по расписанию. И Иннокентий, используя свои многочисленные связи в магазине плитки, совершил невозможное: по маршруту теперь курсируют целых $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. В этой группе вам предлагаются только тесты-серии. Другие дополнительные ограничения отсутствуют.

Примеры

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

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

21
21
31

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

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

Страница: 1 2 3 4 >> Отображать по:

Выбрано

Отменить

Добавить в контест