05/12/2025 14:06:09

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2442. Разработка планов

Ограничения: время – 2000ms/4000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Озимандия разрабатывает планы по предотвращению ядерной войны. Начав с базовой идеи (плана №1), он вносит изменения в него изменения и уточнения, создавая новый план (№2). И так далее. На очередном шаге он берет один из имеющихся `N` планов, вносит в него изменения и получает следующий план (с номером `N+1`). Время от времени ему нужно определять, какой план был ближайшим общим предком для некоторой пары планов.

Напишите программу, которая отслеживает добавление новых планов и определяет общего предка двух планов по запросу.

Формат ввода

Первая строка ввода содержит одно целое число `Q` (`1\ ≤\ Q\ ≤\ 10^6`) – количество запросов. Далее следует `Q` строк, каждая строка содержит один из двух запросов.

+ `x` – добавить новый план на основе плана с номером `x`.
? `x\ y` – вывести ближайшего общего предка для планов с номерами `x` и `y`.

`x` и `y` – номера существующих планов к моменту выполения запроса.

Формат вывода

Вывести для каждого запроса ? одно целое число на отдельной строке – номер плана, который является ближайшим общим предком для обоих планов.

Пример ввода

14
+ 1
+ 1
+ 3
+ 2
+ 3
+ 4
? 7 6
+ 2
+ 4
? 5 8
? 2 8
? 5 2
+ 2
? 10 9

Пример вывода

Рисунок для примера:

07/04/2019	Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 8)
21/10/2024	LCA, обходы (проводит BOGAT) (B)