#114314

Туризм

Темы: [Динамическое программирование на графах] [Применение обхода в глубину]

Король Байтазар считает, что Байтотия — земля, полная красивых достопримечательностей — должна привлечь множество туристов, которые должны потратить много денег, которые в конечном счете должны найти свой путь в королевскую казну. Но реальность далека от мечты. Поэтому король поручил своему советнику изучить этот вопрос. Советник выяснило, что иностранцы держаться подальше от Байтотии из-за ее плохой дорожной сети. В Байтотии $n$ городов соединенных $m$ двусторонними дорогами. Не гарантируется, что от каждого города можно добраться от любого другого города. Советник отметил, что нынешний дорожная сеть не позволяет делать длительные путешествия. А именно, где бы вы не начали поездку, невозможно посетить более 10 городов не прохождения через какой-то город два раза. Из-за ограниченных средств в казне, новые дороги построить нельзя. Вместо этого, Байтазар решил создать сеть туристическо-информационных пунктов (ТИП), которые будут рекламировать короткие путешествия. Для каждого города должен быть ТИП либо в нем, либо в одном из городов, непосредственно связанных с ним дорогой. Кроме того, известна стоимость строительства ТИПа в каждом из городов. Помогите королю найти самый дешевый спосою построить ТИПы, так, чтобы это условие удовлетворялось.

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

Первая строка стандартного ввода содержит два целых числа $n$ и $m$ ($2 \le n \le 20000, 0 \le m \le 25000$), которые задают количество городов и дорог в Байтотии соответственно. Города нумеруются от $1$ до $n$. Вторая строка содержит целые числа $c_i$ ($0 \le ci \le 10000$) — стоимости строительства ТИПов в городах. Затем идет описание дорожной сети. i-я строка содержит два целых числа $a_i, b_i$, которые указывают, что города $a_i$ и $b_i$ связаны дорогой. Существует не более одной дороги между любой парой городов.

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

Выведите одно целое число — общую стоимость строительства всех ТИПов.

Система оценки

Подзадача 1 (22 балла): $1 \le n, m \le 20$

Подзадача 2 (78 баллов): Без дополнительных ограничений. Оценивается потестово. (6 баллов за тест)

Примеры

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

6 6
3 8 5 6 2 2
1 2
2 3
1 3
3 4
4 5
4 6

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

#114315

Соответствие наборов

Темы: [Z-функция, Префикс-функция] [Декартово дерево] [Хеш]

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

Логотип состоит из $n$ вертикальных полос различной высоты. Полосы пронумерованы от $1$ до $n$ слева направо. Логотип описывается перестановкой $(s_1, s_2, ..., s_n)$ чисел $1, 2, ..., n$. Полоса с номером $s_1$ - самая низкая, полоса с номером $s_2$ - следующая по высоте и, наконец, полоса $s_n$ - самая высокая. Фактическая высота полос не имеет большого значения. Вдоль главной улицы расположено $m$ зданий. К вашему удивлению, высота зданий различна. Задача состоит в том, чтобы найти все позиции, на которых логотип соответствует зданиям. Помогите компании и найдите все непрерывные последовательности зданий, которые соответствуют логотипу. Непрерывная последовательность зданий соответствует логотипу, если здание $s_1$ в этой последовательности является самым низким, здание $s_2$ является следующим по высоте и т. д. Например, последовательность зданий высотой $5, 10, 4$ соответствует логотипу, описанному перестановкой $(3, 1, 2)$, поскольку здание №3 (высотой 4) является самым низким, здание №1 - вторым по высоте, а здание №2 - самым высоким.

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

Первая строка стандартного ввода содержит два целых числа $n$ и $m$ $(2 \le n \le m \le 1 000 000)$.

Вторая строка содержит $n$ целых чисел $s_i$, образующих перестановку чисел $1, 2, ..., n$. То есть $1 \le s_i \le n$ и s$_i \neq s_j$ для $i \neq j$.

Третья строка содержит $m$ целых чисел $h_i$ - высоты зданий ($1 \le h_i \le 10^9$ для $1 \le i \le m$). Все числа различные.

В каждой строке числа разделены пробелами.

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

Первая строка стандартного вывода должна содержать целое число $k$ – количество совпадений.

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

Если $k = 0$, ваша программа должна напечатать пустую вторую строку.

Система оценки

В тестах суммарной стоимостью не менее 35 баллов $n \le 5000$ и $m \le 20 000$.

В тестах суммарной стоимостью не менее 60 баллов $n \le 50 000$ и $m \le 200 000$.

Примеры

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

5 10
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9

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

2
2 6

#114317

Воздушные шарики

Темы: [Стек] [Элементарная геометрия]

Организаторы CEOI 2011 собираются устроить вечеринку с кучей воздушных шариков. Всего будет $n$ шариков (они все имеют форму идеального шара), и они будут лежать на одной линии на полу.

Шарики ещё не надуты, и каждый из них изначально имеет нулевой радиус. Ещё, $i$-й шар прикреплён к полу в позиции $x_i$. Они будут надуваться последовательно, слева направо. Когда какой-то шарик надувается, его радиус непрерывно увеличивается, пока не достигнет верхней границы своего размера, $r_i$, либо же не каснётся одного из уже надутых. $\text{[math]}$ Картинка 1: Шары из примера, после надувания.

Организваторы хотели бы оценить, сколько воздуха понадобится для надувания. Найдите, пожалуйста, итоговый радиус каждого шара.

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

В первой строке входных данных содержится целое число $n$ ($1\le n\le 200 000$) – количество шаров.

Следующие $n$ описывают шары. $i$-я из них содержит два целых числа $x_i$ и $r_i$ ($0\le x_i\le 10^9$), $1\le r_i\le 10^9$). Последовательность $x_i$ строго возрастает.

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

Выведите $n$ строк, в $i$-й строке должно быть единственное целое число – радиус $i$-го шара после надувания. Ваш ответ будет считаться верным, если он отличается от правильного не больше, чем на 0.001 в каждом числе.

Система оценки

1. (40 баллов) $n\le 2000$.

2. (60 баллов) $n\le 200000$.

Примеры

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

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

9.000
1.000
4.694

#114318

Траффик

Темы: [Обход в глубину] [Динамическое программирование на графах] [Компоненты сильной связности]

Центр Гдынии расположен на острове посередине реки Кацза. Каждое утро тысячи машин едут из жилых районов на западном берегу в индустриальные на восточном.

Остров можно представить в виде прямоугольника $A\times B$ со сторонами, параллельными осям координат, углами $(0, 0)$ и $(A, B)$.

На острове есть $n$ перекрёстков, пронумерованных натуральными числами от $1$ до $n$. Перекрёсток номер $i$ имеет координаты $(x_i, y_i)$. Если координаты какого-то перекрёстка имеют вид $(0, y)$, то он находится на западном берегу, если $(A, y)$ - на восточном. Перекрёстки соединены дорогами, каждая - отрезок на плоскости, они не пересекаются (кроме концов). Дороги бывают односторонними и двусторонними. Нет никаких мостов и туннелей! Некоторые дороги могут идти по краям прямоугольника.

Поскольку плотность траффика растёт, мэр города нанял Вас (кого же ещё) проверить, достаточно ли текущей сети дорог. Он попросил написать программу, которая по карте города определит для каждого перекрёстка на западном берегу, сколько из него достижимых на восточном.

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

В первой строке входных данных дано четыре целых числа $n$, $m$, $A$ и $B$ ($1\leq n\leq 300 000$, $0\leq m\leq 900 000$, $1\leq A\leq 10^9$, $1\leq B\leq 10^9$. Это количества перекрёстков, дорог и размеры города, соответственно.

В каждой из следующих $n$ строк есть два целых числа $x_i$, $y_i$ ($0\leq x_i\leq A$, $0\leq y_i\leq B$), описывающих координаты перекрёстка номер $i$. Перекрёстки не совпадают.

Следующие $m$ строк описывают дороги, каждая одну. Это описание состоит из трёх чисел: $c_i$ - номер перекрёстка, откуда ($1\leq c_i\leq n$), $d_i$ - куда ($1\leq d_i\leq n$), $k_i\in\{1, 2\}$ - тип дороги (сколькосторонняя). Разные дороги соединяют разные неупорядоченные пары перекрёстков.

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

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

Выведите для каждого перекрёстка на западном берегу в своей строчке количество достижимых из него перекрёстков на восточном берегу.

Выводите в порядке уменьшения $y$-координаты.

Система оценки

1. (30 баллов) $n, m\leq 6 000$.

2. (70 баллов) $n\leq 300 000$, $m\leq 900 000$.

Примечание

$\text{[math]}$

Примеры

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

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

2
0
2

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

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

#114320

Взлом сейфа

Темы: [Динамика по подмножествам] [Динамическое программирование на поддеревьях] [Дерево отрезков, RSQ, RMQ]

Фермер Джон спрятал ключи от трактора в сейфе. Коровы пытаются взломать этот сейф. Сейф защищён сложной парольной системой.

Она организована как подвешенное за вершину 0 дерево из $n$ ($1 \le n \le 20000$) вершин, каждая из которых требует цифру от $0$ до $9$. Вершины пронумерованы от $0$ до $n - 1$.

Единственная информация, которой владеют коровы – что определённые последовательности длины $5$ не появляютя на путях в этом дереве начиная с каких-то стартовых позиций при движении вверх по дереву.

По заданным $m$ ($0 \le m \le 50000$) последовательностям длины $5$, вместе с их стартовой позицией в дереве помогите коровам вычислить сколько паролей будет не подходить.

Вы должны выводить свой ответ по модулю $1234567$.

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

Первая строка ввода содержит два разделённых пробелом целых числа, $n$ и $m$ ($1 \le n \le 20000, 0 \le m \le 50000$) - количество вершин в дереве и количество запрещённых последовательностей соответственно.

В последующих $i$ строках находится описание дерева. Строка $i + 1$ содержит одно целое число $p[i]$, означающее родителя вершины $i$ в дереве ($0 \le p[i] \lt i$).

В последующих $m$ строках находится описание запрещённых последовательностей. Строка $n + i$ содержит два целых числа $v_i$ и $s_i$, разделенные пробелом - стартовую вершину последовательности, и строку из $5$ цифр, которая не встретится в шифре начиная с вершины $v_i$ если двигаться вверх по дереву ($0 \le v_i \lt n$) соответственно.

Гарантируется, что корень дерева находится не менее чем в 4 шагах от $v_i$.

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

Выведите единственное целое число – количество неподходящих конфигураций цифр по модулю $1234567$.

Система оценки

Подзадача 1 (10 баллов): $1 \le n \le 15, 0 \le m \le 15$

Подзадача 2 (15 баллов): $1 \le n \le 1000, 0 \le m \le 2000$

Подзадача 3 (20 баллов): $1 \le n \le 1000, 0 \le m \le 50000$

Подзадача 4 (55 баллов): $1 \le n \le 20000, 0 \le m \le 50000$

Примеры

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

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