|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
2006. Генеалогическое дерево
|
| Статистика | Послать на проверку | Задачу добавил debug |
|
Как-то раз одна большая семья решила узнать побольше о своих предках и дальних родственниках. Покопавшись в архивах, им удалось найти сведения об n людях, которые, возможно, имеют с ними родственные связи (включая даже тех, кто жил несколько веков назад). Конечно, полной информации найти не получилось, поэтому для каких-то людей известны оба родителя, для кого-то – только один, а для кого-то сведений о родителях и вовсе не нашлось. Полученные данные были представлены в виде графа. Вершины графа представляют людей. Направленное ребро, идущее от вершины u к вершине v, означает, что человек с номером u является родителем v. В каждую вершину входит не более двух рёбер. Гарантируется, что циклов в графе нет. Назовём степенью кровного родства между людьми u и v минимальную длину неориентированного пути между ними, проходящего через их общего предка. Примечание: при этом будем считать, что каждая вершина является предком самой себе. Например, на следующем рисунке для людей 5 и 6 степень родства равна 3 (поскольку кратчайший путь, проходящий через их общего предка, содержит три ребра). Для людей 6 и 3 ответом будет 2, поскольку с учётом примечания их общий предок – это вершина 3, и кратчайший путь содержит 2 ребра.  Напишите программу, которая определит степень кровного родства для заданных пар людей. Входные данные В первой строке входных данных записано целое число n – количество людей (2 ≤ n ≤ 104). В следующих n строках записана информация о родителях каждого человека: вначале идёт число 0, 1 или 2 – количество известных родителей, после чего через пробел записаны номера родителей. В следующей строке записано целое число q – количество пар людей, для которых надо определить степень кровного родства (1 ≤ q ≤ 5·105). В следующих q строках содержатся пары целых чисел – номера людей. Выходные данные Выведите q целых чисел – степень кровного родства для каждой пары людей из входных данных. Если у какой-то пары нет общих предков, то выведите -1. Пример Входные данные 6 0 0 1 1 2 2 3 2 2 3 1 4 3 5 6 6 3 2 3 Выходные данные 3 2 -1 |
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Задачи с соревнований и сборов / | Межвузовские олимпиады / | XXII межвузовская олимпиада - 2019 / |
| 2005. F - Пробелы | 2006. | 2007. H - Красивые числа | 2008. I - Седловая точка | 2009. J - Copy-Paste |
| время генерации 0.109 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |