графы

Задана перестановка \((p_1,p_2,\ldots, p_N)\) из \(1\ldots N\), указывающая как произошли посещения.

Для каждого \(i\) от \(1\) до \(N\):

• Если бык \(a_{p_i}\) уже ушёл со своей фермы, то бык \(p_i\) остаётся на своей ферме.
• Иначе бык \(p_i\) уходит со своей фермы на ферму \(a_{p_i}\). Этот визит завершается радостным "moo" произнесённым \(v_{p_i}\) раз (\(0\le v_{p_i}\le 10^9\)).

Вычислите максимально возможное количество "moo" после всех визитов по всем возможным перестановкам \(p\).

Две фишки размещаются на заданном графе. На каждом ходу первый игрок (brain) выбирает фишку, которая должна пройти по одной из выходящих дуг. Другой игрок (hoof) выбирает по какой дуге должна пойти эта фишка. Эти две фишки никогда не могут быть в одной и той же вершине. Если в какой-то момент hoof не может сделать ход, выиграл brain. Если игра продолжается бесконечно - выиграл hoof.

Вам даются \(Q\) запросов (\(1 \leq Q \leq 10^5\)), указывающие стартовые вершины обоих фишек. Для каждого запроса выведите, какой игрок выиграет.

**Замечание: Время на тест для этой задачи 4 сек, (в два раза больше значения по умолчанию).**

На ферму поступили \(M\) различных типов зерна \((2\le M\le 10^5)\). К несчастью, есть только один ящик зерна каждого типа. Каждая из \(N\) коров \((1\le N\le 10^5)\) имеет первый и второй любимые типы зерна. Когда корове приходит время выбирать, она выполняет следующий процесс:

1. Если ящик с её любимым типом еще есть, она берёт его и отходит
2. Иначе если ящик с её вторым любимым типом зерна ещё есть, она берёт его и отходит
3. Иначе она не берёт ничего

Определите минимальное количество коров, которые останутся голодными при оптимальном порядке выбора. Выведите любую перестановку из \(N\) коров (порядок), при которой достигается этот минимум.

ФД намерен сделать серию из \(Q\) изменений (\(0\le Q\le 2\cdot 10^5\)) следующих видов

• D x - деактивировать ферму \(x\), так что она перестанет производить молоко.
• A x y - построить дорогу между двумя активными фермами \(x\) и \(y\).
• R e - удалить \(e\)-ую дорогу, которая была добавлена. (\(e = 1\) - первая дорога, которая была добавлена).

Ферма \(x\) которая активно производит молоко или которая достижима от другой активной фирмы через серию дорог называется "релевантной" фермой. Для каждой фермы \(x\), вычислите максимум \(i\) (\(0\le i\le Q\)) таких, что \(x\) релевантна после \(i\)-го обновления.

D x
A x y
R e

ФД по лени просто назначил корове \(i\) подарок \(i\) для всех \(i\). Теперь коровы собрались и решили переназначить подарки так, чтобы у каждой коровы либо остался изначальный подарок, либо он был заменён на более предпочитаемый подарок.

Для каждого \(i\) от \(1\) до \(N\), выведите наиболее предпочитаемый подарок который она может получить после переназначения.

ФД по лени просто назначил корове \(i\) подарок \(i\) для всех \(i\). Теперь коровы собрались и решили переназначить подарки так, чтобы у каждой коровы либо остался изначальный подарок, либо он был заменён на более предпочитаемый подарок.

Имеется также дополнительное ограничение: подарок может быть переназначен корове, если он изначально был назначен корове такого же типа (Holstein или Guernsey)). Задано \(Q\) (\(1\le Q\le \min(10^5,2^N)\))длин \(N\) строк пород для каждой из них вычислите количество переназначений, соответствующих ей.

На ферме Джона имеется \(N\) амбаров (\(2 \leq N \leq 2\cdot 10^5\)) пронумерованных \(1 \dots N\). Имеется \(N-1\) дорог, где каждая дорога соединяет два амбара и от любого амбара до любого другого можно добраться посредством некоторой последовательности дорог. В \(j\)-ом амбаре имеется \(h_j\) снопов сена (\(1\le h_j\le 10^9\)).

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

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

Изначально имеется \(M\) (\(1\le M\le 2\cdot 10^5\)) пар друзей среди \(N\) (\(2\le N\le 2\cdot 10^5\)) коров Фермера Джона. Коровы пронумерованы \(1\dots N\). Коровы покидают ферму на каникулы одна за другой. В день \(i\), \(i\)-ая корова покидает ферму и все друзья этой коровы которые ещё остались на ферме образовывают новые пары друзей. Сколько новых пар будет образовано всего?

Ферма Джона может быть представлена как ориентированный взвешенный граф, с дорогами (дугами), соединяющими различные вершины и вес каждой дуги есть время, которое требуется чтобы проехать по этой дороге. Каждый день Беси любит путешествовать из амбара (вершина \(1\)) в поле (вершина \(N\)), используя ровно \(K\) дорог и хочет добраться до поля как можно быстрее при этих ограничениях. Однако, в некоторой точке, прекращается поддержка дорог и они начинают ломаться одна за другой, становясь непроходимыми. Помогите Беси определить кратчайший путь от амбара до поля во все моменты времени.

Формально, мы начинаем с полного взвешенного ориентированного графа из \(N\) вершин (\(1\le N\le 300\)) и \(N^2\) дуг: одна дуга для каждой пары \((i, j)\) \(1 \le i, j \le N\), заметим, что имеется \(N\) петель (дуг из \(i\) в \(i\)). После каждого удаления выведите минимальный вес из всех путей из \(1\) в \(N\), проходящих ровно \(K\) (необязательно различных) дуг \(2\le K\le 8\)). Заметим, что после \(i\)-го удаленя в графе остаётся \(N^2-i\) дуг.

Вес пути определяется как сумма весов всех дуг в пути. Заметим, что путь может содержать множество вхождений одних и тех же дуг, и одних и тех же вершин, включая \(1\) и \(N\).

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

Определите максимальную силу по всем "дружественным группам".

Сейчас Эльза создаёт новый неориентированный граф \(G\) с \(N_1\cdot N_2\cdots N_K\) вершинами, каждая из которых помечена \(K\)-плетом \((j_1,j_2,\ldots,j_K)\), где \(1\le j_i\le N_i\). В \(G\) две вершины \((j_1,j_2,\ldots,j_K)\) и \((k_1,k_2,\ldots,k_K)\) соединены ребром, если для всех i \(1\le i\le K\), \(j_i\) и \(k_i\) соединены ребром в \(G_i\).

Определим расстояние между двумя вершинами в \(G\) которые лежат в одной и той же связной компоненте как минимальное количество ребер на пути из одной вершины в другую. Вычислите сумму расстояний между вершиной \((1,1,\ldots,1)\) и каждой вершиной в этой же компоненте в \(G\) по модулю \(10^9+7\).

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

Например, рассмотрим холст \(3\times 3\)

AAB
BBA
BBB

Он может быть раскрашен за 4 касания так:

...    ..B    AAB    AAB    AAB
... -> ... -> ... -> BB. -> BBA
...    ...    ...    BBB    BBB

Невозможно его раскрасить менее чем за 4 касания.

Будучи авангардисткой, Беси намерена покрасить только подрегион холста. Сейчас она рассматривает \(Q\) кандидатов (\(1\le Q\le 1000\)), каждый из которых представляется четырьмя целыми числами \(x_1\), \(y_1\), \(x_2\), \(y_2.\) Это означает, подпрямоугольник состоит из всех ячеек со строками в диапазоне от \(x_1\) до \(x_2\) включительно, и колонками в диапазоне от \(y_1\) до \(y_2\) включительно.

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

Замечание: Время на тест в этой задач ена 50% выше чем по умолчанию, а ограничения оп памяти 512 Мбт - в два раза больше чем по умолчанию.

\(|i-j|\) минут требуется, чтобы передать сообщение от коровы \(i\) к корове \(j\). Однако не все породы готовы взаимодействовать друг с другом, что описано в матрице \(S\) размером \(K \times K\), где \(S_{ij} = 1\) если корова породы \(i\) готова передать сообщение корове породы \(j\) и 0 в противном случае. Необязательно истина то, что \(S_{ij}=S_{ji}\), и даже может быть случай, когда \(S_{ii} = 0\), то есть корова породы \(i\) не будет передавать сообщение корове своей породы.

Определите минимальное количество времени, которое потребуется для передачи сообщения.

Сначала все \(N\) коров (\(2\le N\le 10^5\)) стоят в ряд, корова \(i\) стоит на позиции \(i\). Последовательность перемещений в танце задаётся \(K\) (\(1\le K\le 2\cdot 10^5\)) парами позиций \((a_1,b_1), (a_2,b_2), \ldots, (a_{K},b_{K})\). В каждую минуту \(i = 1 \ldots K\) танца, коровы в позициях \(a_i\) и \(b_i\) меняются позициями. Аналогичные \(K\) обменов произойдут в минуты \(K+1 \ldots 2K\), затем в минуты \(2K+1 \ldots 3K\), и т.д. до истечения \(M\) минут (\(1\le M\le 10^{18}\)) Другими словами

• В минуту \(1\), коровы в позициях \(a_1\) и \(b_1\) меняются позициями.
• В минуту \(2\), коровы в позициях \(a_2\) и \(b_2\) меняются позициями.
• ...
• В минуту \(K\), коровы в позициях \(a_{K}\) и \(b_{K}\) меняются позициями.
• В минуту \(K+1\), коровы в позициях \(a_{1}\) и \(b_{1}\) меняются позициями.
• В минуту \(K+2\), коровы в позициях \(a_{2}\) и \(b_{2}\) меняются позициями.
• и т.д. ...

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

Замечание: время на тест удвоено.

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

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

Имеется \(K\) (\(1\le K\le 10^5\)) билетов доступных для продажи. \(i\)-ый билет можно купить в пункте \(c_i\) (\(1\le c_i\le N\)) за цену \(p_i\) (\(1\le p_i\le 10^9\)) и обеспечить себе доступ ко всем пунктам \([a_i,b_i]\) (\(1\le a_i\le b_i\le N\)). Прежде чем войти в любой пункт, Беси должна купить билет который обеспечивает доступ в этот пункт. Купив однажды билет в пункт, Беси может возвращаться в него в любой момент в будущем.

Для каждого \(i\in [1,N]\), выведите минимальную суммарную цену которую требуется заплатить, чтобы получить доступ к обоим пунктам \(1\) и \(N\), если изначально Беси имела доступ только к пункту \(i\). Если это невозможно, выведите \(-1\).

Эльза пытается угадать это число. Она может задавать вопросы вида "число \(i\) больше или меньше?" для некоторого \(i\) между \(1\) и \(N\), включительно. Беси отвечает "HI", если число \(i\) больше чем \(x+0.5\), или "LO" если число \(i\) меньше чем \(x+0.5\).

При угадывании числа Эльза следует следующей стратегии. Сначала она создаёт список из \(N\) чисел, где каждое число от \(1\) до \(N\) встречается ровно один раз (другими словами, этот список есть перестановка размера \(N\)). Затем она идёт по этому списку спрашивая число по порядку из этого списка.

Однако Эльза пропускает бесполезные вопросы, например, если Эльза сейчас должна спросить про число \(i\), а ранее она спрашивала про число \(j < i\) и Беси отвечала "HI", тогда Эльза не спрашивает про \(i\) и переходит к следующему числу в перестановке. Аналогично, если она раньше спрашивала про \(j > i\) и получала ответ "LO", Эльза не спрашивает про \(i\) и переходит к следующему числу в списке. Можно доказать, что следую такой стратегии, Эльза всегда однозначно определит \(x\) вне зависимости от перестановки, которую создаст.

Если мы конкатенируем все ответы Беси вида "HI" или "Lo" в одну строку \(S\), тогда количество раз, когда Беси сказала "HILO" есть количество подстрок длины \(4\) в строке \(S\), которые равны "HILO".

Беси знает стратегию Эльзы; более того, она также занет точную перестановку, которую Эльза будет использовать. Однако Беси ещё не решила какое использовать число \(x\).

Помогите Беси определить сколько раз она скажет "HILO" для каждого значения \(x\).

1. Каждый браслет - одна замкнутая многоугольная цепочка -- серия вершин (точек), соединённых последовательно отрезками прямых, где первая и последняя точки свопадают (детальнее см. многоугольная цепочка),
2. Браслет не самопересекается (это соответсвует "простой") многоугольной цепочке.
3. Никакие два браслета не пересекаются.

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

К счастью, у Беси есть фонарик. Она выбрала \(M\) (\(1\le M\le 50\)) вертикальных прямых \(x=1, x=2, \ldots, x=M\) и для каждой вертикальной прямой она направила луч вдоль неё от \(y=-\infty\) до \(y=\infty\), записывая цвета всех браслетов, которые она увидела в порядке их появления. По счастью, лучи фонарика не пересекли ни одну вершину ни одной многоугольной цепочки. Более того, для каждого луча каждый цвет появился ровно дважды.

Помогите Беси, используя эту информацию, определить возможно ли чтобы браслеты удовлетворяли всем трём указанным выше условиям.

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

Для каждого \(1 \leq K \leq N\), помогите коровам определить количество классов эквивалентности стартовых состояний: то есть максимальное количество стартовых состояний, которое они могут выбрать, так что никакие два из них не будут эквивалентными. Поскольку эти числа могут быть очень большими, выведите их остатки по модулю \(10^9 + 7\).