ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование школьников. Октябрь 2004

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Галактическая история

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Невероятно трудно одному человеку изучить всю галактическую историю.
С другой стороны каждый дипломат, стремящийся занять как более значимый пост в галактической империи, должен очень хорошо ее знать. Так уронить ложку в присутствии высокопоставленных членов звездной системы Арктура, значит неслыханно их оскорбить (А разве вы не слышали, что последний конфликт между системами Арктура и Альфы Водолея разгорелся всего то из-за одного уроненного стакана).
К счастью в Галактической Академии выяснили, что, например, для дипломатов нижнего ранга достаточно выучить только одну ветвь истории, касающуюся только того кластера звездных систем, в котором он собирается работать. (Действительно, ведь дипломаты нижнего ранга ведут переговоры только между планетами, находящимися в одном звездном кластере. И как нам раньше не приходила такая идея).
С учетом этого очень ценного замечания было решено единый межгалактический курс истории заменить на несколько локализованных курсов, каждый из которых охватывает только ту часть истории, которая касается только одного звездного кластера. Естественно, что историю изучать надо в хронологическом порядке, начиная от зарождения человечества, поэтому историю Земли нужно включить во все сборники локализованных историй. Дальше сложнее: так звездная система Волопаса была колонизирована выходцами из системы Центавры, а значит учебник для системы Волопаса обязательно должен включать раннюю историю системы Центавра.
Для решения вопроса о том, какие этапы истории включать или не включать в тот или иной учебник, специалисты-историки Галактической Академии разбили всеобщую межгалактическую историю на множество мелких вех. Далее все вехи были построены в одно большое дерево (тут помогли вездесущие биологи, которые, как оказалось, всегда пользовались такими деревьями). Корнем этого дерева была объявлена веха, соответствующая ранней истории Земли (до космической колонизации). Ее сыновьями являются вехи, которые соответствуют истории Звездных систем, близких к Солнечной системе (так как они были колонизированы выходцами с Земли) и т.д. Все! Для определения тех вех, которые стоит включать в учебник, осталось всего-навсего быстро определять, находится ли веха A в поддереве с корнем в вехе B.

Исходные данные

В первой строке находится число N (N ≤ 40000), определяющее общее число вех. В следующих N строках находятся описания каждой из вех.
Каждая веха описывается двумя числами: ID - уникальный числовой идентификатор вехи и ParentID - идентификатор вехи, являющейся ее отцом в данном дереве. (ParentID для корня дерева равен -1).
(N+2)-я строка содержит число L (L ≤ 40000) - количество запросов. Следующие L строк содержат описания запросов: два различных числа A и B. Все идентификаторы лежат в пределах от 0 до 40000.

Результат

Для каждого запроса в отдельной строке необходимо вывести:
  • 1, если веха А является корнем поддерева, содержащего веху B.
  • 2, если веха B является корнем поддерева, содержащего веху A.
  • 0, если не верно ни одно из первых двух условий.

Пример

исходные данныерезультат
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19
1
0
0
0
2
Автор задачи: Евгений Крохалев
Источник задачи: Десятый командный чемпионат школьников Свердловской области по программированию (16 октября 2004 года)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1329. Галактическая история