Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

**Замечание: Память на тест 512MB, в два раза больше, чем по умолчанию.**

Беси планирует бесконечное путешествие в стране с $N$ ($1\leq N \leq 10^5$) городами. В каждом городе есть портал и время зацикливания $T_i$. Все $T_i$. являются степенями двойки и $T_1 + \cdots + T_N \leq 10^5$. Если Вы войдёте в портал города $i$ в день $t$, Вы немедленно выйдете из портала в городе $c_{i, t\bmod{T_i}}$.

У Беси есть $Q$ ($1\leq Q \leq 5\cdot 10^4$) планов её путешествия, каждый из которых есть тройка чисел $(v, t, \Delta)$. В каждом плане она начинает в городе $v$ в день $t$. Затем она делает следующее $\Delta$ раз. Она входит в портал текущего города, затем ждёт один день. Для каждого из её планов она хочет узнать, в каком городе она закончит путешествие.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит два разделённых одиночным пробелом целых числа: $N$, количество городов и $Q$, количество запросов.

Вторая строка содержит $N$ разделённых одиночными пробелами целых чисел: $T_1, T_2, \ldots, T_N$ ($1\leq T_i$, $T_i$ степень $2$, и $T_1 + \cdots + T_N \leq 10^5$).

Для $i = 1, 2, \ldots, N$, строка $i+2$ содержит $T_i$ разделённых одиночными пробелами положительных целых чисел, а именно $c_{i, 0}, \ldots, c_{i, T_i-1}$ ($1\leq c_{i, t} \leq N$).

Для $j = 1, 2, \ldots, Q$, строка $j+N+2$ содержит три разделённых одиночными пробелами положительных целых числа, $v_j, t_j, \Delta_j$ ($1\leq v_j \leq N$, $1\leq t_j \leq 10^{18}$, $1\leq \Delta_j \leq 10^{18}$) представляющих $j$-ый запрос.

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите $Q$ строк. $j$-ая строка должна содержать ответ на $j$-ый запрос.

—Войти и решать

Disruption#90030

Ферма Джона состоит из $N$ пастбищ ($2 \leq N \leq 50,000$), попарно соединённых $N-1$ двунаправленными дорожками единичной длины. Известно также, что имеется путь из любого пастбища к любому.

Однако если одну из дорожек заблокировать, то ферма разделится на две части, внутри каждой из которых связность сохранится, а между ними - нет. Поэтому ФД строит $M$ дополнительных дорожек ($1 \leq M \leq 50,000$), каждая из которых имеет положительную целую длину не более $10^9$. Коровы пользуются исходными дорожками, пока это возможно.

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

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

ФОРМАТ ВВОДА (файл disrupt.in):

Первая строка ввода содержит $N$ и $M$. Каждая из последующих $N-1$ строк описывает оригинальную дорожку целыми числами $p$ $q$, где $p$ \neq q$ - пастбища, соединённые этой дорожкой (в интервале $1 \ldots N$). Каждая из оставшихся $M$ строк описывает дополнительную дорожку тремя целыми числами $p$, $q$, $r$, где $r$ длина этой дорожки. Не более одной дорожки пролегает между любыми двумя пастбищами.

ФОРМАТ ВЫВОДА (файл disrupt.out):

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

Двоичные подьемы Дерево отрезков, RSQ, RMQ

—Войти и решать

New Barns#90007

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

Всякий раз когда ФД строит новый амбар, он соединяет его не более чем одной двунаправленной дорожкой с существующим амбаром. Чтобы обеспечить достаточное удаление коров он иногда хочет определить расстояние от определённого амбара до самого дальнего амбара достижимого от этого амбара. Расстояние между двумя амбарами определяется как количество дорожек, по которым нужно пройти от одного амбара до другого.

ФД имеет $Q$ ($1 \leq Q \leq 10^5$) запросов, каждый вида "построить" или "расстояние". Для запроса "построить" ФД строит амбар и соединяет его не более чем с одним из имеющихся амбаров. На запрос "расстояние" ФД спрашивает у Вас от определённого амбара до самого дальнего амбара достижимого от этого амбара по некоторой последовательности дорожек. Гарантируется, что амбар запроса уже построен. Ответьте на запросы ФД.

ФОРМАТ ВВОДА (файл newbarn.in):

Первая строка содержит целое число $Q$. каждая из последующих $Q$ строк содержит запрос. Каждый запрос имеет вид "B p" или "Q k", соответственно построить амбар и соединить его с амбаром $p$ или вывести дальнейшее расстояние по условию задачи от амбара $k$. Если $p = -1$, то новый амбар не соединяется ни с каким из старых. Иначе $p$ - номер амбара в порядке построения. Амбары нумеруются от $1$, т.е. Первый построенный амбар будет иметь номер $1$, второй - $2$, и т.д.

ФОРМАТ ВЫВОДА (файл newbarn.out):

Выведите по одной строке для каждого запроса "расстояние". Заметим, что амбар, который не соединён ни с одним из других амбаров имеет самое дальнее расстояние $0$.

Двоичные подьемы Наименьший общий предок

—Войти и решать