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

Топологическая сортировка#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—Войти и решать

Гномы и Одинокая гора#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—Войти и решать

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):

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

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

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

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

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

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

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

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

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

ОЦЕНИВАНИЕ:

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

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

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

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

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

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

ОЦЕНИВАНИЕ:

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

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

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

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

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

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

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

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

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

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