Страница: << 522 523 524 525 526 527 528 >> Отображать по:

#114091

Темы: [Обход в глубину]

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

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

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

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

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

Примеры

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

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

NO

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

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

YES

#114092

Необычная яблоня

Темы: [Обход в глубину] [Деревья]

У Аркадия в саду есть одна необычная яблоня, с которой иногда необходимо собирать яблоки. Так как яблоня необычная, на ней есть $n$ соцветий, они пронумерованы от 1 до $n$. Соцветие номер 1 находится около корня дерева, любое другое соцветие с номером $i(i>1)$ расположено на верхнем конце ветки, нижний конец которой расположен в соцветии $p_i$.

Когда яблоки созревают, одновременно появляется ровно по одному яблоку в каждом соцветии. В тот же момент все яблоки начинают скатываться вниз по веткам к корню дерева. Каждую секунду все яблоки, кроме находящегося в первом соцветии, одновременно скатываются на одну ветку ближе к корню, то есть, например, из соцветия a яблоко попадет в соцветие $p_a$. Яблоки, находившиеся в первом соцветии, забирает Аркадий. Яблоня необычная, поэтому, если в какой-то момент в одном соцветии оказываются два яблока, они аннигилируют. Так происходит с каждой парой, например, если в соцветие попадет одновременно 5 яблок, то останется только одно яблоко, а если в соцветие попадет одновременно 8 яблок, то не останется ни одного яблока. Таким образом, в каждом соцветии в любой момент времени находится не более одного яблока.

Помогите Аркадию, подсчитайте, сколько яблок он сможет забрать из первого соцветия за один урожай.

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

В первой строке следует целое число $n(2 \le n \le 100000)$ — количество соцветий.

Во второй строке следует последовательность целых чисел $p_2, p_3, ..., p_n$, состоящая из $n−1$ числа, где $p_i$ равно номеру соцветия, в которое скатывается яблоко из соцветия $i$.

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

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

Примеры

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

3
1 2

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

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

5
4 2 5 1

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

#114114

Вложенные коробки с конфетами

Темы: [Бинарный поиск]

В качестве новогоднего подарка Андрей получил коробку с конфетами. Или не совсем коробку. На самом деле он быстро обнаружил, что внутри коробки находятся ещё несколько одинаковых коробок меньшего размера, внутри которых содержатся ещё меньшие коробки и так далее... Формально, скажем что конфета является коробкой уровня 0 , а коробка уровня i содержит в себе a _i коробок уровня i - 1 . Коробка, подаренная Андрею, имеет уровень n .

Сегодня к Андрею в гости придут друзья и он хочет поделиться с ними некоторым количеством конфет, для чего ему придётся открыть некоторое количество коробок. Разумеется, Андрей не может открыть коробку, если она находится внутри ещё не открытой коробки. Ему хотелось бы знать, какое минимальное количество коробок ему потребуется открыть, чтобы достать x конфет. Поскольку Андрей ещё не уверен, сколько друзей к нему сегодня придут, он просит вас решить задачу для нескольких значений x .

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

В первой строке входных данных записаны числа n и m ( 1 ≤ n , m ≤ 300 000 ) — количество коробок и количество вопросов Андрея соответственно.

Во второй строке записаны n целых чисел a ₁ , a ₂ , ..., a _n ( 1 ≤ a _i ≤ 10 ⁹ ).

В третьей строке записаны m чисел x ₁ , x ₂ ..., x _m ( 1 ≤ x _i ≤ 10 ¹² ) — значения количества конфет, для которых Андрей хочет знать ответ. Гарантируется, что каждое значение x _i не превосходит общего число конфет в коробке уровня n .

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

Выведите m целых чисел, i -е из них должно равняться минимальному количеству коробок, которое потребуется открыть Андрею, чтобы получить хотя бы x _i конфет.

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

Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых предыдущих групп, указанных в таблице ниже.

$\text{[math]}$

Примечание

В первом примере единственная конфета спрятана в пяти уровнях коробок.

Во втором примере, чтобы получить 13 конфет, Андрей должен открыть самую большую коробку, затем две коробки уровня 2 , и, наконец, пять из шести имеющихся коробок уровня 1 .

Примеры

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

5 1
1 1 1 1 1
1

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

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

3 3
3 3 3
2 8 13

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

3
5
8

#114134

Суровый корректор

Темы: [Корневая эвристика (sqrt декомпозиция)] [Строки]

По мнению Александра Павловича, текст необычайно красив, если некоторые особые слова (например, «коммунизм», «Ленин», «счастье») встречаются не слишком часто, но и не слишком редко, к тому же достаточно равномерно.

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

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

Он настолько устал от рутинного подсчёта: «а сколько тут особых слов?», «а сколько тут?», что просит вас помочь ему автоматизировать этот процесс.

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

Первая строка входного файла содержит текст длины $L$ ($1 \leq L \leq 10^5$), в котором ищутся особые слова.

Следующая строка содержит $N$ ($1 \le n \le 10^5$) — количество особых слов.

Следующие $n$ строк содержат особые слова. Все особые слова различны. Суммарная длина строк не превосходит $10^5$.

В следующей строке дано $Q$ ($1 \le q \le 10^5$) — количество интересных Александру Павловичу отрезков.

Следующие $q$ строк содержат сами отрезки.

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

Выведите $q$ чисел — количества вхождений особых слов в соответствующий отрезок текста.

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

Тесты к данной задаче состоят из семи групп тестов. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы и всех тестов зависимых групп и теста из условия.

Обозначим за $LEN_{max}$ максимальную длину особого слова.

$n \leq 1000, q = 1$, группа оценивается в $11$ баллов.
$LEN_{max} \leq 1000, q = 1$, группа оценивается в $13$ баллов.
$q = 1$, группа оценивается в $12$ баллов. Группа зависит от 1, 2.
$n \leq 1000, q \leq 10000$, группа оценивается в $21$ балл. Группа зависит от 1.
$LEN_{max} \leq 1000, q \leq 10000$, группа оценивается в $19$ баллов. Группа зависит от 2.
$q \leq 10000$, группа оценивается в $23$ балла. Группа зависит от 1, 2, 3, 4, 5.
полные ограничения, группа оценивается в $1$ балл. Группа зависит от 1, 2, 3, 4, 5, 6.

Примеры

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

abacababa
2
a
aba
3
5 9
2 2
2 6

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

5 0 2

#114217

Винни-Пух и бочки меда

Темы: [Корневая эвристика (sqrt декомпозиция)]

У Винни-Пуха есть $n$ бочек меда. В $i$-й бочке налито $a_i$ меда, а объем бочки равен $b_i$ ($1 \le i \le n$). Винни-Пух хочет полностью заполнить все свои бочки. Для этого он последовательно делает $q$ шагов. На $j$-м шаге он будет наливать мед в бочки с номерами от $l_j$ до $r_j$ ($1 \le j \le q$). В бочку с номером $l_j$ Винни-Пух нальет $c_j$ меда, в следующую бочку он нальет $c_j + d_j$ меда, в следующую $c_j + 2 \cdot d_j$ меда и так далее до бочки с номером $r_j$.

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

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

В первой строке даны два целых числа $n$ и $q$ ($1 \le n, \ q \le 2 \cdot 10^5$).

Во второй строке через пробел даны $n$ целых чисел $0 \le a_1, \ldots, a_n \le 10^5$.

В третьей строке через пробел даны $n$ целых чисел $1 \le b_1, \ldots, b_n \le 10^9$.

В следующих $q$ строках даны по четыре целых числа $l_j$, $r_j$, $c_j$, $d_j$ ($1 \le l_j \le r_j \le n$, $0 \le c_j, \ d_j \le 10^5$, $1 \le j \le q$).

Гарантируется, что $a_i < b_i$ для всех $1 \le i \le n$.

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

В единственной строке выведите $n$ целых чисел -- ответ для каждой из бочек.

Примеры

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

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

0 3 3 2 1

Страница: << 522 523 524 525 526 527 528 >> Отображать по:

Выбрано

Отменить

Добавить в контест