Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Волонтеры

(Время: 2 сек. Память: 16 Мб Сложность: 62%)

В проведении межпланетной олимпиады по информатике принимает участие большое количество андроидов. Андроиды, придумывающие задачи, пишущие условия и разрабатывающие наборы тестов, являются членами научного комитета. Те андроиды, которые обеспечивают работоспособность компьютеров и установленного на них программного обеспечения, являются членами технического комитета. Есть третья большая группа андроидов, участвующих в организации и проведении многих других мероприятий, – это волонтеры.

У каждого волонтера есть свой непосредственный начальник в научном комитете и свой непосредственный начальник в техническом комитете. У каждого члена научного комитета, кроме его председателя, есть свой непосредственный начальник – другой член научного комитета. У каждого члена технического комитета, кроме его председателя, также есть свой непосредственный начальник, являющийся членом технического комитета.

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

Все n волонтеров получают уникальные номера от одного до n, после чего выстраиваются друг за другом в порядке возрастания своих номеров. После этого m членов научного комитета, также имеющие уникальные номера от одного до m, по очереди, в порядке возрастания их номеров, выбирают себе подчиненных следующим образом. Вначале, первый член научного комитета выбирает себе в подчинение некоторое количество волонтеров, стоящих в данный момент в строю подряд друг за другом. После этого те, кого он выбрал, выходят из строя, а он сам встает в строй на то место, где стояли его новоиспеченные подчиненные, заменяя собой сразу несколько андроидов в строю. Затем второй член научного комитета выбирает себе подчиненных из тех, кто теперь стоит в строю и заменяет их собой аналогично первому. Так этот процесс продолжается, и каждый последующий член научного комитета может выбрать себе в подчинение находящихся в строю волонтеров и членов научного комитета. Последним выбирает себе подчиненных председатель научного комитета, и он должен выбрать всех андроидов, кто на тот момент будет находиться в строю.

После того, как в строю останется только председатель научного комитета, аналогичный процесс повторяется с самого начала, но уже с членами технического комитета. Важно то, что номера волонтеров при этом сохраняются и волонтеры выстраиваются в том же порядке, что и при выборе подчиненных членами научного комитета.

Считается, что член научного комитета может конфликтовать с членом технического комитета, если один и тот же волонтер подчиняется, возможно, не напрямую, и члену научного комитета, и члену технического комитета. Из этого определения, в частности, следует, что председатель научного комитета всегда может конфликтовать с председателем технического комитета. Несложно понять, что от общего количества таких возможных конфликтов между андроидами зависит то, насколько качественно будет проведена олимпиада.

Требуется написать программу, которая для каждого члена научного комитета подсчитывает количество членов технического комитета, с которыми он может конфликтовать, и определяет суммарное количество таких конфликтов.

Входные данные

Первая строка входного файла INPUT.TXT содержит числа n, m и k (1 ≤ n, m, k ≤ 100 000) – количество волонтеров, членов научного комитета и членов технического комитета соответственно.

Последующие n строк содержат по два числа ai и bi (1 ≤ ai ≤ m, 1 ≤ bi ≤ k) – номер начальника соответствующего волонтера среди членов научного комитета и номер начальника соответствующего волонтера среди членов технического комитета.

Следующая строка содержит (m–1) чисел ci (i = 1..(m–1), i < ci ≤ m) – номер начальника i-го члена научного комитета. Председатель научного комитета имеет номер m.

Следующая строка содержит (k-1) чисел di (i = 1..(k–1), i < di ≤ k) – номер начальника i-го члена технического комитета. Председатель технического комитета имеет номер k.

Гарантируется, что все входные данные корректны, то есть они получены в результате процесса назначения подчиненных, описанного выше.

Выходные данные

Первая строка выходного файла OUTPUT.TXT должна содержать одно число – суммарное количество искомых конфликтов.

Пример

INPUT.TXTOUTPUT.TXT
14 3 4
1 2
1 1
2 1
2 4
3 3
3 3 4
11

Пояснения к примеру

В представленном примере только второй член научного комитета и второй член технического комитета не могут конфликтовать друг с другом.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 A. POBEDA-2014
 B. Список школ
 C. Межрегиональная олимпиада
 D. Дом Мэра
 E. Светофоры
 F. Кондиционеры
 G. Конфеты
 H. Волонтеры

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru