На чемпионате Урала-2004 была задача "Одноклассники".
Вкратце её содержание таково:
Ученице Тане поступило задание от директора школы оповестить свой класс о том, что 3 первых завтрашних занятия отменяются в связи с отключением электричества. Таня очень ловко справилась с этим. Сначала она решила позвонить Лене, затем Кате, а потом Маше. В то время, пока она звонила Кате, Лена, уже узнавшая новость, звонила Мише и т.д. В результате весь класс в миг узнал об отмене занятий.
В задаче требовалось узнать минимальное время, за которое весь класс мог узнать о приятной новости.
Но время шло, и летом Таня пошла работать в рекламное агентство "Карамболь". Рекламное агентство "Карамболь" имеет чётко выраженную иерархическую структуру. В её вершине находится генеральный директор. Он имеет своих подчинённых, которые, в свою очередь, также могут иметь подчинённых и т.д. В один прекрасный день Таня придумала метод, помогающий увеличить отдачу от рекламы на 110%. Она сразу же позвонила своей начальнице, затем своей подруге Лене, находящейся у неё в подчинении, потом Кате и Маше. Те, в свою очередь, быстро перезвонили своим друзьям и т.д. Определите, какое наименьшее время понадобится для того, чтобы всё агентство "Карамболь" узнало о сказочно эффективном методе Тани. Но учтите, что телефоны рекламного агентства настроены так, чтобы каждый сотрудник мог говорить либо со своим непосредственным начальником, либо со своим непосредственным подчинённым (иначе и нельзя — девушки прекрасно заменяют работу продолжительным общением по телефону, если им разрешить чуток больше). Каждый телефонный разговор занимает ровно одну минуту.
Исходные данные
В первой строке находится одно число N (N ≤ 100000) — количество служащих в фирме "Карамболь".
Каждый служащий имеет свой уникальный ID — число от 1 до N.
Далее следует N строк. Строка с номером K содержит список подчинённых K-го служащего,
завершающийся нулём. В последней строке находится одно число — Танин ID. Напомним, что в агентстве "Карамболь" у каждого сотрудника, кроме генерального директора, есть ровно один непосредственный начальник.
Результат
Выведите одно число — минимальное время в минутах, за которое вся компания "Карамболь" узнает о гениальном методе простой девочки по имени Таня.
Пример
исходные данные | результат |
---|
10
2 3 0
4 5 7 0
6 9 0
0
0
8 10 0
0
0
0
0
2
| 5
|
Замечания
Обратите внимание: несмотря на пример в тексте, Таня и другие сотрудники могут звонить своему начальнику и подчинённым в любом порядке.
Автор задачи: Евгений Крохалев
Источник задачи: IX Чемпионат Урала по спортивному программированию. Екатеринбург, УрГУ, 19-24 апреля 2005 г.