Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2442. Разработка планов
Наименьший общий предок (LCA)Олимпиадные задачи на русском языке
| 07/04/2019 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 8) |
Ограничения: время – 2000ms/4000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
Пример вывода
3 2 2 2 1
