Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Max Flow#90350

Фермер Джон установил новую систему из \(N-1\) труб чтобы транспортировать молоко между \(N\) стойлами в его амбаре (\(2 \leq N \leq 50,000\)), последовательно пронумерованными \(1 \ldots N\). Каждая труба соединяет пару стойл, и все стойла связаны друг с другом посредством последовательности труб.

ФД проталкивает молоко между K парами стойл (\(1 \leq K \leq 100,000\)). Для \(i\)-ой такой пары вам сообщают \(s_i\) и \(t_i\), начальную и конечную точки пути между которыми молоко проталкивается на единичной скорости. ФД опасается, что некоторые стойла могут переполниться молоком, проталкиваемым через них. Помогите ФД определить максимальное количество молока, которое можно протолкнуть через любое стойло. Если молоко проталкивается вдоль пути от \(s_i\) до \(t_i\), тогда считается, что оно проталкивается не только через конечные точки(стойла) \(s_i\) и \(t_i\), но также и через каждое стойло на пути между ними.

ФОРМАТ ВВОДА (файл maxflow.in):

Первая строка ввода содержит \(N\) и \(K\).

Каждая из следующих \(N-1\) строк содержит два целых числа \(x\) и \(y\) (\(x \ne y\)) описывающих трубу между стойлами \(x\) и \(y\).

Каждая из следующих \(K\) строк содержит два целых числа \(s\) и \(t\), описывающих конечные точки-стойла пути, по которому проталкивается молоко.

ФОРМАТ ВЫВОДА (файл maxflow.out):

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

Наименьший общий предок

—Войти и решать

New Barns#90007

Фермер Джон заметил, что его коровы чаще спорят, если располагаются слишком близко. Поэтому он хочет открыть серию новых амбаров и распространить коров по ним.

Всякий раз когда ФД строит новый амбар, он соединяет его не более чем одной двунаправленной дорожкой с существующим амбаром. Чтобы обеспечить достаточное удаление коров он иногда хочет определить расстояние от определённого амбара до самого дальнего амбара достижимого от этого амбара. Расстояние между двумя амбарами определяется как количество дорожек, по которым нужно пройти от одного амбара до другого.

ФД имеет \(Q\) (\(1 \leq Q \leq 10^5\)) запросов, каждый вида "построить" или "расстояние". Для запроса "построить" ФД строит амбар и соединяет его не более чем с одним из имеющихся амбаров. На запрос "расстояние" ФД спрашивает у Вас от определённого амбара до самого дальнего амбара достижимого от этого амбара по некоторой последовательности дорожек. Гарантируется, что амбар запроса уже построен. Ответьте на запросы ФД.

ФОРМАТ ВВОДА (файл newbarn.in):

Первая строка содержит целое число \(Q\). каждая из последующих \(Q\) строк содержит запрос. Каждый запрос имеет вид "B p" или "Q k", соответственно построить амбар и соединить его с амбаром \(p\) или вывести дальнейшее расстояние по условию задачи от амбара \(k\). Если \(p = -1\), то новый амбар не соединяется ни с каким из старых. Иначе \(p\) - номер амбара в порядке построения. Амбары нумеруются от \(1\), т.е. Первый построенный амбар будет иметь номер \(1\), второй - \(2\), и т.д.

ФОРМАТ ВЫВОДА (файл newbarn.out):

Выведите по одной строке для каждого запроса "расстояние". Заметим, что амбар, который не соединён ни с одним из других амбаров имеет самое дальнее расстояние \(0\).

Двоичные подьемы Наименьший общий предок

—Войти и решать

Берляндия атакует#55177

В этой задаче Вам вновь придется помочь Берляндии. Эта страна состоит из n городов, некоторые пары из которых соединены двусторонними дорогами, каждая дорога характеризуется своей длиной. Все города пронумерованы числами от 1 до n, столица имеет номер 1. Время от време ни Президент объезжает страну, посещая города страны. Целью каждой поездки является один из городов, к которому он едет из столицы вдоль дорог одним из кратчайших путей.

В далекие времена (когда задачи на алгоритм Дейкстры вызывали сложность) специальное ведомство составила такой набор дорог T, вдоль которого можно было проехать из столицы в любой город, причем единственным образом. Разумеется, путь по дорогам из набора T из столицы в каждый город являлся кратчайшим. Особо умные жители страны попросту называли этот набор дорог "деревом кратчайших путей". Известно, что Президент пользовался дорогами из T во время своих поездок. За прошедшие годы этот набор перестал быть секретным, и, поэтому, стал объектом повышенного внимания берляндских экстремистов. У специального ведомства новое задание. Для каждого города кроме столицы необходимо вычислить кратчайшее расстояние до него, при условии, что та дорога по которой Президент должен был закончить свой путь в этот город является атакованной и проезжать по ней нельзя.

Входные данные
В первой строке входного файла записана пара целых чисел n и m (2 ≤ n≤ 4000; n−1 ≤ m ≤100000), где n — количество городов в стране, а m— количество дорог в этой стране. Далее в m строках содержатся описания дорог, по одной дороге в строке. Каждая дорога задается четверкой целых чисел a_j, b_j, l_j, t_j , где a_j, b_j это номера городов, соединяемых дорогой (1 ≤ a_j,b_j ≤ n; a_j≠b_j), l_j — ее длина (1 ≤ l_j≤ 10⁵), а t_j равно 1 если дорога принадлежит дереву кратчайших путей и 0 в противном случае.

Гарантируется, что набор T удовлетворяет описанным выше свойствам. Между парой городов может быть более одной дороги. Все дороги двусторонние.

Выходные данные
Выведите n−1 число в строку через пробелы. i-ое число должно быть равно либо длине кратчайшго пути из столицы в город i+1, при условии, что по той дороге из T, которой Президент заканчивал свой путь в этот город, передвигаться нельзя, либо -1, если добраться до города i+1 вообще невозможно.

Дерево отрезков, RSQ, RMQ Наименьший общий предок Разреженные таблицы (sparse table)

✓ 1✗ 0—Войти и решать

Воздушные потоки#24765

Колобок ушёл от бабушки и поехал путешествовать. Неожиданно для себя он забрёл в страну Ивэнлэнд. Первые трудности встали на его пути: Колобка и вход в страну отделял огромный ров с водой, которая, как известно, не очень хорошо влияет на нашего героя. К счастью, повсюду рас- положены воздушные потоки, которые могли поднимать того, кто на них встает, на определённую высоту. Страна не просто так названа Ивэнлэнд, поэтому все высоты, на которые могут поднять героя воздушные потоки — это чётные числа.

Представим воздушные потоки как массив h[1..n] из n натуральных чисел — высот потоков. Для каждого 1 ≤ i ≤ n посчитаем G[i] — индекс ближайшего элемента слева, строго большего h[i]. Более формально, g[i] = max{j | j < i и h[j] > h[i]}. Если i = 1 или до h[i] нет ни одного элемента больше него, то G[i] считается равным 0.

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

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

Помогите Колобку сделать оптимальное изменение, которое позволит добиться, чтобы сумма S(h), описанная выше, после проделанного действия была минимальна.

Формат входного файла
В первой строке входного файла даны числа n, m (1 ≤ n ≤ 10⁵ , 1 ≤ m ≤ 10⁹ ) — количество воздушных потоков и максимальное значение, на которое можно увеличить высоту одного из них. Во второй строке даны высоты воздушных потоков h[i] (1 ≤ h[i] ≤ 10⁹ ). Гарантируется, что все высоты — чётные числа.

Формат выходного файла
В единственной строке выходного файла выведите одно целое число — минимальную искомую сумму.

Ввод	Вывод
3 100 4 2 6	4
3 2 4 2 6	5
3 10 2 2 2	4

Деревья Наименьший общий предок Разреженные таблицы (sparse table)Структуры данных

✓ 2✗ 151 200средняяВойти и решать