Антивирусная IT-компания имеет официальную иерархическую структуру управления. В ней есть босс – единственный сотрудник, над которым нет начальника. Каждый из остальных сотрудников подчинён ровно одному сотруднику – своему начальнику. Начальник может иметь нескольких подчинённых и отдавать или передавать приказы любому из них. Приказы могут передаваться от одного сотрудника другому только по цепочке, каждый раз от начальника к его подчинённому. Сотрудник А главнее сотрудника Б в этой иерархии, если А может отдать или передать приказ сотруднику Б непосредственно, или через цепочку подчинённых. Босс главнее любого сотрудника. Оказалось, что все сотрудники объединены ещё в одну организованную подобным образом тайную иерархическую структуру, производящую компьютерные вирусы. В тайной структуре может быть другой босс, а у сотрудников – другие начальники. Будем называть пару сотрудников А и Б устойчивой, если А главнее Б и в основной, и в тайной иерархических структурах. Требуется написать программу, определяющую количество устойчивых пар в компании.
В первой строке задано число N – количество сотрудников компании (1 ≤ N ≤ 100 000). Во второй строке – N целых чисел ai, где ai = 0, если в официальной иерархии сотрудник с номером i является боссом, в противном случае ai равно номеру непосредственного начальника сотрудника номер i. В третьей строке – N целых чисел bi, где bi = 0, если в тайной иерархии сотрудник с номером i является боссом, в противном случае bi равно номеру непосредственного начальника сотрудника номер i. Нумерация сотрудников ведется с единицы в том порядке, в каком они упомянуты во входном файле.
Выходной файл должен содержать единственное число – количество устойчивых пар.
Данная задача содержит три подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
3 0 3 1 0 1 1
2
5 2 0 1 3 4 3 1 0 2 4
7
После прохождения монеты по трубке ширина этой трубки уменьшается на 1. Монета не может пройти по трубке ширины 0. Если монета достигла узла, из которого она не может дальше двигаться вниз, автомат останавливается и ждёт, когда в него бросят следующую монету
Изначально в каждом узле лабиринта находится по игрушке. Когда монета попадает в узел первый раз, игрушка, находящаяся в этом узле, достаётся игроку, бросившему эту монету.
Панкрату понравилась игрушка, которая находится в узле с номером \(v\).
Требуется написать программу, которая определяет, сколько монет должен бросить в автомат Панкрат, чтобы получить игрушку из узла \(v\).
В первой строке входного файла задано число \(n\) — количество узлов в лабиринте. В последующих n строках заданы описания всех узлов, в \(k\)-й из этих строк описан узел с номером \(k\).
Описание k-го узла состоит из четырех целых чисел: \(a_k\), \(u_k\), \(b_k\), \(w_k\). Если из \(k\)-го узла выходит левая трубка, то \(a_k\) — номер узла, в который она ведет (\(k\) < \(a_k\) <= \(n\)), а \(u_k\) — её ширина. Если левой трубки нет, то \(a_k\) = \(u_k\) = 0. Если из \(k\)-го узла выходит правая трубка, то \(b_k\) — номер узла, в который она ведет (\(k\) < \(b_k\) <= \(n\)), а \(w_k\) — её ширина. Если правой трубки нет, то \(b_k\) = \(w_k\) = 0.
В последней строке задано целое число \(v\) (1 <= \(v\) <= \(n\)) — номер узла, в котором находится игрушка, понравившаяся Панкрату.
Гарантируется, что во все узлы, кроме первого, входит ровно одна трубка
Выходной файл должен содержать одно число — количество монет, которое необходимо бросить в автомат Панкрату, чтобы получить игрушку, которая находится в узле \(v\). Если получить выбранную игрушку невозможно, выведите число −1.
Данная задача содержит две подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
1 <= \(n\) <= 100
1 <= \(u_k\); \(w_k\) <= 300
Подзадача оценивается в 50 баллов.
1 <= \(n\) <= \(10^5\)
1 <= \(u_k\); \(w_k\) <= \(10^9\)
Подзадача оценивается в 50 баллов.
В первом примере первая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 1, 3 и 4:
Вторая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 2 и 6:
Третья монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 5 и 7:
7 2 1 3 2 0 0 6 3 4 1 5 1 0 0 0 0 7 2 0 0 0 0 0 0 0 0 0 0 5
3
4 0 0 2 1 4 1 3 1 0 0 0 0 0 0 0 0 3
-1
Со стародавних времён в поморских деревнях рукодельницы вышивали жемчугом на прямоугольных полотенцах, состоящих из одинаковых клеток. Вышивка начиналась с пришивания жемчужины к полотенцу в центре одной из клеток. Чтобы пришить новую жемчужину, рукодельница делала стежок из клетки, уже содержащей жемчужину, в соседнюю с ней по горизонтали или вертикали свободную клетку. Новая жемчужина пришивалась в центре клетки на конце стежка. Этот процесс повторялся, пока не заканчивались жемчужины.
Одно из таких праздничных полотенец находится в музее. К сожалению, некоторые части узора были утеряны, но описание полотенца сохранилось. Дирекция музея планирует восстановить один из прямоугольных фрагментов полотенца, но не ещё не решила какой именно. Затраты на восстановление фрагмента зависят от количества связных частей узора, попавших на этот фрагмент. Часть узора считается связной, если от любой её жемчужины можно по стежкам перейти к любой другой её жемчужине, не выходя за границы фрагмента. Дирекция всегда относит любые две жемчужины, между которыми можно перейти по стежкам, к одной и той же связной части узора.
Требуется написать программу, вычисляющую количество связных частей узора для каждого из заданных фрагментов.
Первая строка входных данных содержит два целых числа a и b — размеры полотенца в клетках по горизонтали и вертикали.
Вторая строка содержит два числа \(n\) и \(q\) — количество жемчужин в узоре и количество фрагментов соответственно.
Следующие (\(n − 1\)) строк содержат описания стежков. Каждый стежок имеет один из следующих видов:
• \(h \times y\) означает, что клетки с координатами \((x, y)\) и \((x + 1, y)\) содержат жемчужины, соединённые горизонтальным стежком (\(1 \le x \le a − 1; 1 \le y \le b\));
• \(v \times y\) означает, что клетки с координатами \((x, y)\) и \((x, y + 1)\) содержат жемчужины, соединённые вертикальным стежком (\(1 \le x \le a; 1 \le y \le b − 1\)).
Так как неизвестно в каком порядке рукодельница наносила стежки, их описания следуют в произвольном порядке. При этом гарантируется, что узор был получен в результате процесса, описанного в условии задачи.
Следующие \(q\) строк описывают фрагменты. Каждое описание содержит четыре целых числа \(x_1\), \(y_1\), \(x_2\) и \(y_2\) — координаты левой нижней и правой верхней клетки фрагмента (\(1 \le x_1 \le x_2 \le a; 1 \le y_1 \le y_2 \le b\)).
Выходные данные должны содержать \(q\) строк, где \(i\)-я строка содержит количество связных частей узора в \(i\)-м фрагменте.
Пояснение к тесту из условия
4 3 8 4 v 1 1 h 1 1 h 2 1 v 2 1 v 2 2 h 1 3 h 3 1 1 1 4 3 3 2 4 3 3 1 3 1 1 2 3 3
1 0 1 2
Путешествие по стране никогда не бывает простым, особенно когда не существует прямого сообщения между городами. Группа туристов хочет добраться в город Метрополис, используя сеть железных дорог, которая соединяет n городов, пронумерованных от 1 до n. Город, из которого выезжает группа, имеет номер 1, Метрополис имеет номер n.
На железной дороге постоянно функционируют m маршрутов поездов. Каждый маршрут определяется последовательностью городов, перечисленных в том порядке, в каком их проезжает поезд, обслуживающий этот маршрут. В каждом маршруте для каждой пары соседних городов задано время, за которое поезд этого маршрута проезжает перегон между этими городами. При этом поезда разных маршрутов могут проезжать один и тот же перегон за разное время.
По пути в Метрополис группа может садиться на поезд и сходить с поезда в любом городе маршрута, не обязательно в начальном или конечном. При этом, можно сойти с поезда маршрута i, пересесть на поезд маршрута j, возможно сделать еще несколько пересадок, а потом вновь сесть в поезд того же маршрута i.
Туристы предъявляют высокие требования к выбору способа проезда в Метрополис.
Во-первых, суммарное время, проведенное в поездах, должно быть минимальным.
Во-вторых, среди всех способов с минимальным временем нахождения в поездах предпочтительным является тот способ, для которого сумма квадратов промежутков времени, непрерывно проведенных в поезде между двумя пересадками, максимальна. Назовём эту сумму качеством путешествия.
Время, проведенное вне поездов, не учитывается.
Требуется написать программу, которая по описаниям имеющихся маршрутов поездов определит минимальное время, которое группе туристов придется провести в поездах, а также максимальное качество путешествия с таким временем.
В первой строке входных данных заданы два целых числа (2 ≤ n ≤ 106, 1 ≤ m ≤ 106) — количество городов и количество маршрутов соответственно.
Далее в m строках содержится описание маршрутов.
Описание каждого маршрута начинается с целого числа si — количество перегонов в маршруте с номером i (1 ≤ si ≤ 106). Далее следуют (2si + 1) целых чисел, описывающих города маршрута и время проезда перегона между соседними городами маршрута, в следующем порядке: vi, 1, ti, 1, vi, 2, ti, 2, vi, 3, ..., ti, si, vi, si + 1, где vi, j — номер j-го города маршрута, ti, j — время проезда перегона между j-м и (j + 1)-м городом (1 ≤ vi, j ≤ n, 1 ≤ ti, j ≤ 1000).
Гарантируется, что s1 + s2 + ... + sm ≤ 106. Никакие два города в описании маршрута не совпадают. Гарантируется, что с помощью имеющихся маршрутов можно добраться из города с номером 1 в город с номером n.
Выходные данные должны содержать два целых числа — минимальное суммарное время, которое придется провести в поездах, и максимальное качество пути с таким временем.
В первом примере группа туристов отправится прямым маршрутом в Метрополис.
Во втором примере не оптимально проехать напрямую по первому маршруту, так как время в поезде при этом не будет минимальным возможным. Поэтому они отправятся на поезде по маршруту 1 из города 1 в город 2, затем на поезде по маршруту 2 из города 2 в город 3, а затем снова на поезде по маршруту 1 из города 3 в город 5. При этом сумма квадратов промежутков времени, проведенных в поездах между пересадками, равна 32 + 12 + 52 = 35.
В третьем примере добраться из города 1 в город 4 за минимальное время можно, пересаживаясь с маршрута 1 на маршрут 2 в любом из городов 2, 3 или 4. Максимальное качество путешествия достигается при пересадке в городе 2: 12 + 92 = 82.
Обратите внимание, что второй и третий примеры не удовлетворяют ограничениям первой и второй подзадачи, решение будет протестировано на этих подзадачах, если оно пройдет первый тест из примера. Все тесты из примера подходят под ограничения подзадач 3 – 7, решение будет проверяться на тестах этих подзадач только в случае прохождения всех тестов из примера.
2 1 1 1 3 2
3 9
5 2 4 1 3 2 3 3 5 5 10 4 3 4 2 2 1 3 4 1
9 35
5 2 3 1 1 2 2 3 3 4 3 2 2 3 3 4 4 5
10 82