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

Топологическая сортировка#68537

Задан ориентированный ациклический граф с $n$ вершинами и $m$ ребрами. Также задана перестановка вершин графа. Необходимо проверить, является ли данная перестановка топологической сортировкой.

В первой строке даны два числа $n$ и $m$ — количество вершин и ребер в графе соответственно ($1 \leq n, m \leq 10^5$). В следующих $m$ строках заданы пары чисел $u_i, v_i$, означающие, что в графе есть ребро из вершины $u_i$ в вершину $v_i$. В последней строке задана перестановка из $n$ элементов.

Выведите "YES" (без кавычек), если данная перестановка является топологической сортировкой и "NO" в противном случае.

Применение обхода в глубину Топологическая сортировка

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

65817#65817

В далёком заснеженном города Снежнокрибирске очень мало пеших тропинок, так как город просто не успевает их чистить, потому люди передвигаются в основном только на внедорожниках: ездят в магазин, отвозят детей в школу, ездят на работу и так далее.
В один из последних дней перед зимними каникулами ребятам в школе задали проект на каникулы, который можно делать как самому, так и в группе, но не более 3 человек. Но так как проект связан с совместной работой, а в городе нет никакой связи: ни телефонной, ни интернета, то ребята решили собираться у кого-нибудь дома, чтобы делать проект вместе. Так как проект может делать до трёх человек, то ученики составили карту своих домов в городе, а также отметили на них тропинки. У них встал вопрос о том, как делать большинство проектов максимальным возможным количеством человек, но так, чтобы как можно меньше учеников делали проект одни. Помогите ребятам по описанию карты их города и тропинкам составить возможный план, как им лучше распределить проекты между собой.

Формат входных данных
На первой строке подаются два числа N, M (1 <= N,M <= 100) – количество домов и тропинок между ними соответственно.
Далее на M строках подаются дорожки в виде номеров домов (если существует дорога 1-2, то значит существует дорожка и 2-1).
Формат выходных данных
Выведите на первой строке количество учеников, которые делают проект в одиночку.
На второй – количество групп учеников, делающих проект в паре.
На третьей – количество групп учеников, делающих проект втроём.

Примечание: ребята стараются разбиться на группы по максимуму человек (по 3), если остался кто-то один, но он мог делать проект не один, то стараемся минимизировать одиночек.

Алгоритмы на графах Поиск компонент связности Применение обхода в глубину

✓ 33✗ 58800средняяВойти и решать

Возрастающие пути#44510

Дано дерево на n вершинах (связный неориентированный ациклический граф c n−1 рёбрами), где у каждого ребра есть вес w. Назовём простой путь длины k возрастающим , если существует такое целое x>=2, что вес первого ребра пути делится на x, второго ребра — делится на x², ……, вес k-го ребра делится на x^k.

Требуется найти максимальную длину k возрастающего пути, где k — количество рёбер в нём.

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

В первой строке вводится единственное целое число n (1 <= n <= 100000) - число вершин в дереве.

В следующих n−1 строках вводятся по три целых числа u, v, w ( 1<= v <= n, 1<= w <= n, u ≠ v, 1 <= w <= 10⁷) - номера вершин, которые соединяет очередное ребро, и его вес.

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

Выведите одно целое число k - максимальную длину возрастающего пути.

Примечание

Простым путем называется такой путь, что все вершины в нем различны.

В 1-м примере есть путь длины 2: 3 — 1 — 2. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.

Во 2-м примере есть путь длины 3: 3 — 4 — 5 — 6. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.

Примеры

№	Входные данные	Выходные данные
1	4 1 2 8 1 3 6 1 4 3	2
2	6 1 2 2 2 3 4 3 4 2 4 5 4 5 6 8	3

Алгоритмы на графах Арифметические алгоритмы (Теория чисел)Обход в глубину Применение обхода в глубину

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

Построение#38569

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

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

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

Входные данные
Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны.

Выходные данные
В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений.

Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 2 3 3 4 1 4 4 1	No

Обход в глубину Топологическая сортировка

✓ 8✗ 25900средняяВойти и решать

Лабиринт Tac Toe#38130

Беси любит искать пути в лабиринтах и играть в "крестики-нолики". Фермер Джон придумал для неё способ играть в обе игры одновременно!
Первое - "крестики-нолики" - вместо размещения X и O на решётке 3×3, коровы играют с М и О на решётке 3×3. Во время хода корова может поставить М или О в любую пустую ячейку (в отличие от стандартной игры, где один игрок всегда ставит X, а другой всегда О). Победитель этой игры тот, кто первый получит слово 'MOO' горизонтально, вертикально или по диагонали. В обратном порядке тоже засчитывается, то есть 'OOM' тоже выигрышная комбинация. Как и в стандартной игре, возможно заполнить всё поле и никто не выиграл. Ход в игре указывается 3 символами 'Mij' или 'Oij', где i и j в интервале 1…3 и указывают строку и столбец, в которые ставится соответствующий символ 'M' или 'O'.

Фермер Джон спроектировал для Беси квадратный лабиринт, представляющий решётку из N×N ячеек (3≤N≤25). Некоторые ячейки, включая все граничные ячейки, содержат большие стоги сена, предотвращающие Беси от захода в эти ячейки. Беси может свободно двигаться во все другие ячейки лабиринта предпринимая шаги в в обычных направлениях -север, юг, запад, восток. Некоторые ячейки содержат листок бумаги, на котором написан ход для "крестиков ноликов". По ходу тго, как Беси двигается по лабиринту, каждый раз, когда она попадает на такую ячейку, она должна сделать соответствующий ход в игре "крестики-нолики", в которую она играет параллельно с движением по лабиринту. Если соответствующая ячейка в "крестиках-ноликах" уже занята, то она не предпринимает никаких действий. У неё нет противника в игре "крестики-нолики", но некоторые из ячеек лабиринта могут противоречить её цели составить слово 'MOO'.

Если Беси останавливает игру "крестики-нолики" сразу после победы, определите количество различных выигрышных конфигураций в "крестиках-ноликах", которые она может сгенерировать, двигаясь соответственно в лабиринте.

ФОРМАТ ВВОДА
Первая строка содержит N.
Лабиринт определяется следующими N строками, каждая из которых содержит 3N символов. Каждая ячейка описывается блоком из 3 символов: '###' для стены, '...' для пустой ячейки, 'BBB' для ячейки в которой стартует Беси, ход для "крестиков-ноликов". Ровно одна ячейка содержит 'BBB'.

ФОРМАТ ВЫВОДА
Выведите количество различных выигрышных комбинаций для "крестиков-ноликов" (возможно 0), которые Беси может сгенерировать движением по лабиринту, остановившись после победы.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 ##################### ###O11###...###M13### ###......O22......### ###...######M22###### ###BBB###M31###M11### ###...O32...M33O31### #####################	8	В этом примере имеется 8 выигрышных комбинаций, которые Беси может достичь: O.M .O. MOM O.. .O. .OM O.M .O. .OM O.. .O. MOM O.. ... OOM ..M .O. OOM ... .O. OOM ... ... OOM Пояснения к одной из них: O.. ... OOM Здесь Беси сначала посещает ячейку O11, затем двигается в нижний коридор, посещая O32, M33, O31. Игра прекращается, поскольку Беси выиграла.

Обход в глубину Применение обхода в глубину

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

*Производство деталей#34975

Предприятие «Авто-2010» выпускает двигатели для известных во всём мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за pi секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке.

Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдёт наименьшее время, за которое можно произвести деталь с номером 1.

Входные данные
Первая строка входного файла содержит число n (1≤ n ≤ 100000) — количество деталей двигателя. Вторая строка содержит n натуральных чисел p₁, p₂, p_n, определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 10⁹ секунд.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-я строка содержит число деталей ki, которые требуются для производства детали с номером i, а также их номера. В i-й строке нет повторяющихся номеров деталей. Сумма всех чисел k_i не превосходит 200000.

Известно, что не существует циклических зависимостей в производстве деталей.

Выходные данные
В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел k чисел — номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.

Ввод	Вывод
3 100 200 300 1 2 0 2 2 1	300 2 2 1
2 2 3 1 2 0	5 2 2 1
4 2 3 4 5 2 3 2 1 3 0 2 1 3	9 3 3 2 1

Обход в глубину Топологическая сортировка

✓ 14✗ 521 000средняяВойти и решать

Красота фейерверка#33127

В лаборатории теоретической пиротехники изучают новые технологии организации

фейерверков. Фейерверк представляется как корневое дерево, а поскольку в мощном

фейерверке его элементы также взрываются, порождая новые фейерверки, то ученые вводят

операцию возведения корневого дерева в степень.

Корневое дерево содержит одну или несколько вершин. Одна из вершин выделена и

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

является родителем. При этом от любой вершины можно добраться до корня,

последовательно переходя от вершины к ее родителю. Вершина, которая не является

родителем никакой другой вершины, называется листом. Если вершина x является

родителем вершины y, то вершина y является ребенком вершины x. Будем говорить, что

вершина и ее родитель соединены ребром.

На рис. 1 показан пример корневого дерева с корнем в вершине 1. Родителем вершин

2 и 3 является вершина 1, родителем вершины 4 является вершина 2. Вершины 2 и 3 — дети

вершины 1, а вершина 4 — ребенок вершины 2. Листьями являются вершины 3 и 4.

Рис. 1. Пример корневого дерева с корнем в вершине 1, листьями 3 и 4.

Фейерверк задается своим базовым деревом T и мощностью m. Фейерверк представляется деревом, которое получается в результате возведения дерева T в степень m. Операция возведения дерева в степень устроена следующим образом. Если m = 1, то результат T¹ — само дерево T. Для m > 1 рассмотрим дерево T^{m – 1} . Выполним следующую операцию: для каждого листа x дерева T^{m – 1} создадим копию дерева T и назначим лист x родителем корня соответствующей копии. Получившееся дерево будет деревом T^m .

На рис. 2 показано дерево, представленное на рис. 1, в степенях 1, 2 и 3.

Рис. 2. Пример возведения дерева в степени 1, 2 и 3

Путем в дереве называется последовательность вершин, в которой две соседние

вершины соединены ребром. Все вершины в пути должны быть различны.

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

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

фейерверк. На рис. 3 приведен путь в дереве T², содержащий максимальное количество

вершин. Таким образом, красота фейерверка с базовым деревом T и мощностью 2 равна 10.

Рис. 3. Путь в дереве T² , содержащий максимальное количество вершин.
Требуется написать программу, которая по описанию дерева T и натуральному числу m определяет красоту фейерверка с базовым деревом T и мощностью m.

Формат входных данных

Первая строка входных данных содержит два натуральных числа n и m — количество

вершин в базовом дереве фейерверка T и его мощность (3 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000).

Вторая строка описывает дерево T и содержит (n – 1) целых чисел: p2, p3, …, pn —

номера родителей вершин 2, 3, …, n, соответственно (1 ≤ pi ≤ i – 1).

Формат выходных данных

Требуется вывести одно целое число — красоту фейерверка, представляемого

деревом T^m.

Ввод	Вывод
4 2 1 1 2	10

Динамическое программирование Динамическое программирование Динамическое программирование на поддеревьях Обход в глубину Применение обхода в глубину

✓ 3✗ 211 100средняяВойти и решать

Гномы и Одинокая гора#30710

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

Гномы разделились на два отряда, которые начали свои поиски с пещер u₀ и v₀, соответственно. Гномы каждого из отрядов перемещаются вместе. На обследование пещеры у отряда гномов уходит ровно одна минута, после чего каждый отряд быстро перемещается по переходу в одну из соседних пещер. При этом гномы никогда не заходят в пещеру, если они или другой отряд в ней уже побывали. Оба отряда никогда не заходят в одну и ту же пещеру. Если хотя бы один из отрядов гномов не может переместиться в соответствии с этими правилами, оба отряда сразу прекращают поиски сокровищ.

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

Формат входных данных
В первой строке число n (2 ≤ n ≤ 200 000) — число пещер в Одинокой горе. В следующих n−1 строках заданы переходы между пещерами. В каждой строке записаны номера двух пещер v и u, соединенных переходом (1 ≤ v, u ≤ n). В следующей строке заданы номера пещер v₀ и u₀, в которых исходно находятся два отряда гномов (1 ≤ v₀, u₀ ≤ n, v₀ != u₀).

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

Ввод	Вывод	Пояснение
6 1 2 2 3 3 4 4 5 5 6 4 5	2
8 1 2 2 3 3 4 2 5 5 6 3 7 7 8 1 8	4

Деревья Обход в глубину Применение обхода в глубину

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

Олег и двоичные последовательности#30708

Олег очень любит двоичные последовательности — последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из n элементов.
Для выписанной последовательности Олег посчитал Z-функцию.

Z-функцией последовательности s₁, . . . , s_n называется массив z[1..n], в котором:

• z[1] = 0;
• Если i > 1, то z[i] равно длине наибольшего общего префикса последовательности s и суффикса последовательности s, начинающегося с i-й позиции. Иначе говоря, z[i] равно максимальному k, такому что s₁ = s_i , s₂ = s_i+1, . . . , s_k = s_i+k−1.

Например, для последовательности s = h0, 0, 1, 1, 0, 0, 1i Z-функция следующая: z = h0, 1, 0, 0, 3, 1, 0i.
Записав в тетради последовательность и ее Z-функцию, Олег лег спать. Пока он спал, его младший брат Егор прокрался в комнату и закрасил фломастером последовательность и некоторые значения Z-функции. Проснувшись, Олег заинтересовался, сколько различных двоичных последовательностей он мог вечером написать в тетради, чтобы незакрашенные значения Z-функции были правильными.

Найдите число искомых последовательностей и выведите его по модулю 10⁹ + 7. Заметьте, что Олег мог и ошибиться при вычислении Z-функции, в этом случае ни одна последовательность не подходит и ответ равен 0.
Формат входных данных
В первой строке входного файла находится целое число n — длина исходной двоичной последовательности (1 ≤ n ≤ 1000). Во второй строке входного файла находятся n целых чисел z[1], . . . , z[n], где z[i] — значение Z-функции в позиции i, или −1, если значение в i-й позиции было закрашено (−1 ≤ z[i] ≤ n).

Формат выходных данных
В выходной файл выведите единственное число — остаток от деления числа подходящих двоичных последовательностей на число 10⁹ + 7.

Ввод	Вывод
3 0 0 1	2
4 0 0 1 0	0
3 0 3 -1	0
3 -1 -1 -1	8

Пояснение
В первом примере подходят последовательности {0, 1, 0 } и { 1, 0, 1 }.
Во втором примере не существует ни одной двоичной последовательности длины 4 с заданной Z-функцией.
В третьем примере z[2] = 3, что противоречит определению Z-функции, поэтому ответ 0.
В четвертом примере подходит любая двоичная последовательность длины 3.

Обход в глубину Применение обхода в глубину Разбор случаев

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

Топологическая сортировка#24753

Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать.

Входные данные: В первой строке содержатся два натуральных числа n и m (1≤n≤10⁵, 1≤m≤10⁵) — количество вершин и рёбер в графе соответственно. Далее в m строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно (нумерация вершин начинается с 1).

Выходные данные: Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, требуется вывести −1.

Примеры

№	Входные данные	Выходные данные
1	4 4 1 4 4 3 4 2 3 2	1 4 3 2

Обход в глубину Топологическая сортировка

✓ 717✗ 1 848600лёгкаяВойти и решать

Why Did the Cow Cross the Road III#90434

Ферма Джона представляет собой квадратную решётку из $N \times N$ полей ($2 \leq N \leq 100$). Определённые пары соседних полей (север-юг или запад-восток) разделены дорогами, и высокий забор идёт вокруг периметра всей решётки, не давая коровам возможности покинуть ферму. Коровы могут свободно перемещаться с любого поля на любое соседнее поле (на сервер, юг, запад, восток), хотя они предпочитают переходить дороги только когда это абсолютно необходимо.

Имеется $K$ коров ($1 \leq K \leq 100, K \leq N^2$) на ферме, каждая расположена в различном поле. Пара коров называется "далёкой", если для того чтобы одна корова смогла посетить другую, необходимо перейти хотя бы одну дорогу. Помогите ФД посчитать количество пар удалённых коров.

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

Первая строка ввода содержит $N$, $K$, $R$. Следующие $R$ строк описывают $R$ дорог существующие между парами соседних полей. Каждая строка имеет вид $r$ $c$ $r'$ $c'$ (целые числа в интервале $1 \ldots N$), указывающих, что имеется дорога между соседними полями (строка $r$, колонка $c$ и строка $r'$, колонка $c'$). Последние $K$ строк описывают местоположение $K$ коров (строка, колонка).

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

Выведите количество пар "далёких" коров.

Поиск компонент связности

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

Moocast#90367

$N$ ($1 \leq N \leq 200$) коров Фермера Джона хотят организовать безопасную сеть передачи сообщений.

Каждая корова получает "воки-токи". Каждый "воки-токи" имеет ограниченный радиус передачи: "воки-токи" с мощностью $P$ может передавать сигнал на расстояние не более $P$. Заметим, что "воки-токи" однонаправленный: чтобы получить сигнал от другого "воки-токи", нужно чтобы он имел соотвествующую мощность.К счастью, коровы могут передавать по эстафете сообщения другу другу (в том числе и чужие) и поэтому нет необходимости для каждой коровы быть способной непосредственно передать сообщение каждой другой.

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

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

Первая строка ввода содержит $N$.

Каждая из следующих $N$ строк содержат $x$ и $y$ координаты одной коровы ( целые числа в диапазоне $0 \ldots 25,000$) за которыми следует $p$, мощность "воки-токи" этой коровы.

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

Напишите одну строку - максимальное количество коров, которым можно передать информацию от одной коровы.

графы Поиск компонент связности

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

Moocast#90361

$N$ ($1 \leq N \leq 1000$) коров Фермера Джона хотят организовать безопасную систему для передачи важных сообщений.

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

Коровам нужно решить сколько денег необходимо потратить на "воки-токи". Если они потратят \$X, они получат "воки-токи", способно передавать на расстояние до $\sqrt{X}$. То есть, квадрат расстояния между коровами стоит не более $X$ чтобы обеспечить их коммуникацией.

Помогите коровам определить минимальное целое $X$ такое, что сообщение от любой коровы сможет достичь любой другой коровы.

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

Первая строка ввода содержит $N$.

Каждая из $N$ последующих строк содержит $x$ и $y$ координаты одной коровы. И то и другое - целое в интервале $0 \ldots 25,000$.

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

Напишите в одну строку целое $X$ - минимальное количество денег, которое коровы должны потратить на "воки-токи"

Бинарный поиск по ответу графы Поиск компонент связности

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

Connecting Two Barns#90130

Ферма Джона состоит из множества $N$ полей $(1 \leq N \leq 10^5)$, последовательно пронумерованных $1 \ldots N$. Между этими полями имеется $M$ двунаправленных дорожек $(0 \leq M \leq 10^5)$, соединяющих пары полей.

На этой ферме имеется два амбара - один в поле $1$, другой в поле $N$. ФД хочет быть уверен, что имеется путь между двумя амбарами последовательностью дорожек. Оно готов построить до двух новых дорожек, чтобы добиться своей цели. Стоимость построения дорожки между полями $i$ и $j$ есть $(i-j)^2$.

Помогите ФД определить минимальную стоимость сделать так, чтобы амбары $1$ и $N$ стали достижимы друг для друга.

ФОРМКАТ ВВОДА (с клавиатуры / stdin):

Каждый входной тест содержит $T$ под тестов ($1\le T\le 20$), все из которых должны быть решены правильно, чтобы пройти этот тест.

Первая строка ввода содержит $T$, за которым следуют $T$ подтестов.

Каждый подтест начинается с двух целых чисел $N$ и $M$. Каждая из последующих $M$ строк содержит два целых числа $i$ и $j$, означающих путь между двумя различными полями $i$ и $j$. Гарантируется, что имеется не более одного пути между любыми двумя полями. и что сумма $N+M$ для всех подтестов не более $5 \cdot 10^5$.

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите $T$ строк. $i$-ая строка должна содержать одно целое число, минимальную стоимость для $i$-го подтеста.

графы Поиск компонент связности реализация

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

Wormhole Sort#90113

Коровы Фермера Джона устали от ежедневных сортировок перед выходом из амбара. Они получили Ph.D по квантовой физике и готовы ускорить этот процесс.

Этим утром, как обычно $N$ коров ($1 \leq N \leq 10^5$), последовательно пронумерованных $1 \dots N$, находятся в амбаре на различных позициях, также пронумерованных $1 \dots N$, так что корова $i$ находится в позиции $p_i$. Однако этим утром имеется $M$ туннелей ($1 \leq M \leq 10^5$), которые пронумерованы $1 \dots M$, при этом туннель $i$ двунаправленно связывает позиции $a_i$ и $b_i$ и имеет ширину $w_i$ ( $1\le a_i,b_i\le N, a_i\neq bi, 1\le w_i\le 10^9$ ).

В любой момент времени две коровы, расположенные на противоположных концах туннеля могут параллельно поменяться позициями через него. Коровы могут таким образом меняться позициями сколько угодно раз пока корова $i$ не окажется в позиции $i$ для $1 \leq i \leq N$.

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

ОЦЕНИВАНИЕ:

Тесты 3-5 удовлетворяют ограничениям $N,M\le 1000.$
Тесты 6-10 не имеют дополнительных ограничений.

ФОРМАТ ВВОДА:

Первая строка содержит два целых числа $N$ и $M$.

Вторая строка содержит $N$ целых чисел $p_1, p_2, \dots, p_N$. Гарантируется, что $p$ есть перестановка чисел $1\ldots N.$

Для каждого $i$ между $1$ и $M$, строка $i+2$ содержит целые числа $a_i$, $b_i$, и $w_i$.

ФОРМАТ ВЫВОДА:

Одно целое число: наибольшая минимальная ширина туннеля, в которую поместится коров во время процесса сортировки. Если коровы не используют туннели во время сортировки выведите $-1$.

Бинарный поиск по ответу Поиск компонент связности

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

Fence Planning#90082

У Фермера Джона $N$ коров, последовательно пронумерованных d $1 \ldots N$ ($2 \leq N \leq 10^5$). Они организованы в сложную социальную структуру "moo networks" - маленькие группы коров взаимодействуют внутри группы, но не с другими группами.

Каждая корова расположена в точке $(x,y)$ на двумерной карте фермы. И нам известны $M$ ($(1 \leq M < 10^5)$) пар коров, принадлежащих к одной и той же группе.

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

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

Первая строка ввода содержит $N$ и $M$. Каждая из следующих $N$ строк содержит $x$ и $y$ - координаты коров (неотрицательные целые числа не более $10^8$). Каждая из следующих $M$ строк содержит два целых числа $a$ и $b$, описывающих принадлежность коров с номерами $a$ и $b$ к одной группе. Каждая корова присутствует как минимум в одной из таких пар. Никакие пары во вводе не повторяются.

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

Выведите минимальный периметр, удовлетворяющий ограничениям ФД.

Поиск компонент связности

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

Icy Perimeter#90070

Фермер Джон собирается выпускать и продавать мороженое. Он построил машину, которая производит шарики мороженого, но, к несчастью, немного неправильной формы.

Конфигурация мороженого, которое производится машиной, может быть описано решёткой $N \times N$ grid ($1 \leq N \leq 1000$):

##....
....#.
.#..#.
.#####
...###
....##

Каждый символ '.' представляет пустое место, а каждый символ '#' представляет $1 \times 1$ квадратную ячейку мороженого.

К несчастью, сейчас машина работает не очень хорошо и может производить несколько несвязанных сгустков мороженого (на картинке сверху их два). Сгусток мороженого называется связным, если из любой ячейки сгустка можно добраться до любой другой ячейки, перемещаясь в соседнюю по одному из четырёх направлений (север, юг, запад, восток).

ФД хочет найти площадь и периметр сгустка, который имеет наибольшую площадь. Площадь сгустка равна количеству символов '#' в его картинке. Если несколько сгустков имеют одинаковую площадь, он хочет знать минимальный периметр из них. На рисунке выше, маленький сгусток имеет площадь 2 и периметр 6, а больший сгусток имеет площадь 13 и периметр 22.

Заметим, что сгусток может иметь "дыру" внутри (пустое пространство, окружённое мороженым). В таком случае граница "дыры" также учитывается в периметре сгустка. Сгусток может находиться внутри другого сгустка, в этом случае они рассматриваются как независимые сгустки. Например, ниже представлен сгусток площади 1 внутри сгустка площади 16:

#####
#...#
#.#.#
#...#
#####

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

Первая строка ввода содержит $N$, а следующие $N$ строк описывают вывод машины. Присутствует, как минимум, один символ '#'.

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

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

Задачи на моделирование Клеточная геометрия Поиск компонент связности

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

Milk Visits#90046

Фермер Джон построил $N$ ($1 \leq N \leq 10^5$) ферм, соединённых $N-1$ дорогами, формируя дерево (то есть, каждая ферма достижима от любой другой, и отсутствуют циклы). Каждая ферма содержит коров, чья марка Guernsey или Holstein.

$M$ друзей ФД ($1 \leq M \leq 10^5$) часто посещают его фермы. Во время визита друга $i$, ФД идёт с эти другом по уникальному маршруту от фермы $A_i$ до фермы $B_i$ (возможен случай, когда $A_i = B_i$). Дополнительно они могут попробовать некоторое количество молока вдоль пути, по которому они идут. Поскольку большинство друзей ФД сами фермеры, у них есть сильные предпочтения по молоку. Некоторые из его друзей пьют молоко только коров Guernsey, а оставшиеся пьют только молоко Holstein. Любой из друзей ФД будет счастлив только если он сможет попить предпочитаемое молоко во время визита.

Определите, каждый ли друг останется счастлив после визита.

ОЦЕНИВАНИЕ:

Тесты 2-5 удовлетворяют $N\le 10^3, M\le 2\cdot 10^3.$

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

Первая строка содержит два целых числа $N$ и $M$.

Вторая строка содержит строку длину длины $N$. $i$-ый символ строки есть 'G' если корова на $i$-ой ферме Guernsey, или 'H', если корова на $i$-ой ферме Holstein.

Каждая их следующих $N-1$ строк содержит два целых числа $X$ и $Y$ ($1 \leq X, Y \leq N$), указывающих, что существует дорога между фермами $X$ и $Y$.

Последующие $M$ строк содержат целые числа $A_i$, $B_i$ и символ $C_i$. $A_i$ и $B_i$ представляют конечные точки пути $i$'-го друга, а $C_i$ либо G либо H - тип молока, предпочитаемый $i$-ым другом.

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

Выведите двоичную строку длины $M$. $i$-ый символ строки должен быть '1' если $i$-ый друг будет счастлив, или '0' в противном случае.

графы Деревья Поиск компонент связности

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

Milking Order#90027

$N$ коров ($1 \leq N \leq 10^5$), фермера Джона, пронумерованных $1 \ldots N$, разработали социальную иерархию, в соответствии с которой ФД доит их каждое утро.

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

Наблюдения ФД приоритезированы, поэтому его цель - максимизировать значение $X$ так, чтобы выполнились условия первых $X$ наблюдений. Если несколько порядков дойки могут удовлетворять $X$ наблюдениям, он выбирает тот, в котором корова с меньшим номером доится раньше. Иными словами, если несколько порядков дойки удовлетворяют этим условиям, ФД выбирает лексикографически наименьший. Порядок $x$ является лексикографически меньшим, чем порядок $y$, если для некоторого $j$, , $x_i = y_i$ для всех $i < j$ и $x_j < y_j$ (другими словами два порядка идентичны до некоторой точки, в которой $x$ меньше чем $y$).

Помогите ФД определить наилучший порядок дойки его коров.

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

Первая строка содержит числа $N$ и $M$. Каждая из следующих $M$ строк описывает одно наблюдение. Строка $i+1$ описывает наблюдение $i$ и начинается с количества коров $m_i$ в этом наблюдении, за которым следует список из $m_i$ целых чисел, определяющих порядок коров в этом наблюдении. Сумма $m_i$ не превышает $200,000$.

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

Выведите $N$ разделённых пробелом целых чисел дающих перестановку чисел of $1 \ldots N$, содержащую порядок в котором ФД должен доить своих коров.

Бинарный поиск по ответу графы Топологическая сортировка

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

Milking Order#90025

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

1. Некоторые коровы настаивают чтобы их доили раньше - в соответствии с их социальным статусом. Например, корова 3 имеет наивысший статус, корова 3 имеет средний статус, а корова 5 имеет низкий статус, то корову 3 нужно доить первой, затем корову 2 и затем корову 5.

2. Некоторые коровы могут настаивать, чтобы их доили в определённой позиции внутри порядка. Например, корова 4 может настаивать, чтобы её доили второй среди всех коров.

По счастью, ФД всегда может подоить своих коров в порядке, удовлетворяющем всем условиям.

К несчастью, корова 1 заболела, поэтому ФД хочет подоить эту корову как можно раньше, чтобы раньше отпустить её в амбар отдыхать и выздоравливать. Помогите ФД определить самую раннюю позицию, в которой можно будет подоить корову 1.

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

Первая строка содержит $N$, $M$ ($1 \leq M < N$), $K$ ($1 \leq K < N$), указывающая, что у ФД $N$ коров, $M$ из которых организованы в социальную иерархию, $K$ из которых требуют, чтобы их подоили в определённой позиции порядка. Следующая строка содержит $M$ различных целых чисел $m_i$ ($1 \leq m_i \leq N$). Коровы, представленные в этой строке должны доиться в порядке, в котором они появились в этой строке. Следующие $K$ строк содержат по по два целых числа $c_i$ ($1 \leq c_i \leq N$) и $p_i$ ($1 \leq p_i \leq N$), указывающих, что корова $c_i$ должна быть подоена на позиции $p_i$.

Гарантируется, что ФД может сконструировать порядок доения, удовлетворяющий всем условиям.

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

Выведите самую раннюю позицию, на которой можно подоить корову 1.

графы реализация Топологическая сортировка

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