Алгоритмы на графах

Поле представляет собой прямоугольник с угловыми вершинами в точках \((0,0)\) and \((A,B)\). ФД построил \(n\) вертикальных изгородей (\(0 \leq n \leq 25,000\)) в различных позициях \(a_1 \ldots a_n\) (\(0 < a_i < A\)); каждая изгородь проходит от точки \((a_i, 0)\) до точки \((a_i, B)\). Он также построил \(m\) горизонтальных изгородей (\(0 \leq m \leq 25,000\)) в в различных позициях \(b_1 \ldots b_m\) (\(0 < b_i < B\)); каждая изгородь, проходит из \((0, b_i)\) в \((A, b_i)\). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на \((n+1)(m+1)\) регионов.

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

Например, ФД мог построить изгороди так:

+---+--+
|   |  |
+---+--+
|   |  |  
|   |  |
+---+--+

и открыть их так:

+---+--+
|      |  
+---+  +  
|      |  
|      |
+---+--+

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

Поле представляет собой прямоугольник с угловыми вершинами в точках \((0,0)\) and \((A,B)\). ФД построил \(n\) вертикальных изгородей (\(0 \leq n \leq 2000\)) в различных позициях \(a_1 \ldots a_n\) (\(0 < a_i < A\)); каждая изгородь проходит от точки \((a_i, 0)\) до точки \((a_i, B)\). Он также построил \(m\) горизонтальных изгородей (\(0 \leq m \leq 2000\)) в в различных позициях \(b_1 \ldots b_m\) (\(0 < b_i < B\)); каждая изгородь, проходит из \((0, b_i)\) в \((A, b_i)\). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на \((n+1)(m+1)\) регионов.

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

Например, ФД мог построить изгороди так:

+---+--+
|   |  |
+---+--+
|   |  |  
|   |  |
+---+--+

и открыть их так:

+---+--+
|      |  
+---+  +  
|      |  
|      |
+---+--+

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

Беси и её подружки участвуют в чемпионате. Всего имеется N (1 <= N <= 2000) команд. Каждой команде назначено уникальное ID в интервале 1...2^30-1. Чемпионат с выбыванием - после каждой игры ФД выбирает, какая команда выбывает из турнира, и она больше не участвует ни в каких играх. Турнир заканчивается, когда остаётся ровно одна команда.

ФД заметил необычное свойство счёта в матчах: В любой игре суммарный счёт двух команд всегда будет побитовым исключающим ИЛИ (XOR) ID этих команд. Например, если играют команды с ID 12 и 20, то 24 очка будет набрано в этой игре, поскольку 01100 XOR 10100 = 11000.

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

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

Первая строка содержит одно целое число N. Последующие N строк содержат N ID команд.

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

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

Примечание Один способ набрать 37 таков: 3 и 9, 9 выиграла. В турнире остаются 6 9 10. Затем 6 и 9, побеждает 6. Остаются 6 и 10. Наконец 6 и 10 и 10 побеждает. Общее количество очков: (3 XOR 9) + (6 XOR 9) + (6 XOR 10) = 10 + 15 + 12 = 37. Замечание: Побитовый XOR, чато обозначаемый ^, это побитовая операция, которая выполняется независимо над каждой позицией двух двоичных представлений целых чисел. 1 в позиции получается только если в этой позиции в разных числах находятся разные значения (1 и 0 или 0 и 1). Например 10100 (десятичное 20) XOR 01100 (десятичное 12) = 11000 (десятичное 24)

Амбар описывается решёткой \(N \times N\) (\(2 \leq N \leq 20\)) символов, некоторые из них пусты, некоторые заняты. Бесси начинает в левом нижнем углу (1,1) и должна пройти в правый верхний угол \(N,N\). Вы можете управлять ею посредством последовательности инструкций вида "вперёд", "повернись влево на 90 градусов", "повернись вправо на 90 градусов". Вы хотите задать кратчайшую последовательность, которая приведёт ее к цели. Есл инструкицю выполнить невозможно, Бесси пропускает её и переходит к следующей инструкции.

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

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

3
EHE
EEE
EEE

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

9

В этом примере Инструкции "Вперёд, Вправо, Вперёд, Вперёд, Влево, Вперёд, Влево, Вперёд, Вперёд" приведут Бесси к назначению вне зависимости от начальной ориентации.

Problem credits: Brian Dean

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

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

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

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

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

Для своего последнего шоу, они купили огромный мощный лазер - такой большой, что они не смогли перместить его легко из того места, где он был приобретен. Он хотят послать свет от лазера в амбар ФД. И лазер, и амбра могут рассматриваться как точки на плоскости - карте фермы ФД. В панах коров направить лазер так, чтобы он послал лч света горизонтально или вертикально (то есть вдоль оси x или вдоль оси y). Затем они планируют ментяь направление луча посредством зеркал, чтобы направить луч в амбар.

На этой ферме есть \(N\) (\(1 \leq N \leq 100,000\)) точек изгороди, расположенных в различных точках на плоскости, (и отличающихся также от точек лазера и амбара), на которых могут крепится зеркала. Коровы могут выбрать не крепить зеркало к некоторым точкам, тогда луч просто проходит через эту точку без поворотов (не меняя направление). Если коровы монтируют зеркало в точке изгороди, они выравнивают его диагонально так / или так \, что соответсвенно пернаправляет горизонтальный в вертикальный и наоборот.

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

Беси начинает в комнате \((1,1)\), - единственной комнате, в которой изначально был включён свет. В некоторых комнатах она найдёт переключатели, которые могут переключать свет в других комнатах. Например, в комнате \((1,1)\) может находиться переключатель света в комнате \((1,2)\). Беси может ходить только в те комнаты, где уже горит свет. И также она может переходить из комнаты \((x,y)\) только в четыре соседние комнаты \((x-1,y)\), \((x+1,y)\), \((x,y-1)\), \((x,y+1)\) (или, возможно, в меньшее количество комнат, если она находится на границе решётки.

Определите максимальное количество комнат, в которые Беси может включить свет.

ПРИМЕР ВЫВОДА

5

Здесь Беси может использовать переключатель в комнате \((1,1)\), чтобы включить свет в комнатах \((1,2)\) и \((1,3)\). Затем она может перейти в комнату \((1,3)\) и включить свет в комнате \((2,1)\), где она может включить свет в комнате \((2,2)\). Переключатель в комнате \((2,3)\) недоступен для неё, поскольку он находится в комнате, где свет не включён. Поэтому Беси может посетить не более 5 комнат.

Авторы: Austin Bannister и Brian Dean

Беси начинает в комнате \((1,1)\), - единственной комнате, в которой изначально был включён свет. В некоторых комнатах она найдёт переключатели, которые могут переключать свет в других комнатах. Например, в комнате \((1,1)\) может находиться переключатель света в комнате \((1,2)\). Беси может ходить только в те комнаты, где уже горит свет. И также она может переходить из комнаты \((x,y)\) только в четыре соседние комнаты \((x-1,y)\), \((x+1,y)\), \((x,y-1)\), \((x,y+1)\) (или, возможно, в меньшее количество комнат, если она находится на границе решётки.

Определите максимальное количество комнат, в которые Беси может включить свет.

ПРИМЕР ВЫВОДА

5

Здесь Беси может использовать переключатель в комнате \((1,1)\), чтобы включить свет в комнатах \((1,2)\) и \((1,3)\). Затем она может перейти в комнату \((1,3)\) и включить свет в комнате \((2,1)\), где она может включить свет в комнате \((2,2)\). Переключатель в комнате \((2,3)\) недоступен для неё, поскольку он находится в комнате, где свет не включён. Поэтому Беси может посетить не более 5 комнат.

Авторы: Austin Bannister и Brian Dean

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

Однако подождите! Каждая клетка имеет свой цвет, и каждый цвет имеет различные свойства:

• Если клетка red (красная), то в неё ходить нельзя
• Если клетка pink (розовая), то в неё можно ходить
• Если клетка orange (оранжевая), то в неё можно ходить, но Беси станет пахнуть как апельсин.
• Если клетка blue (синяя) , то она содержит пираний, которые позволят Беси пройти только если она пахнет как апельсин.
• Если клетка purple (пурпурная), то Беси проскальзывает в следующую клетку в этом направлении (если только в следующую клетку можно заходить). Если следующая клетка также пурпурная, Беси продолжает скользить, пока не попадёт в не пурпурную клетку или остановится перед непроходимой клеткой. Скольжение одной клетки засчитывается как один шаг. Пурпурные клетки также удаляют запах.

(Пример ниже подробнее поясняет "пурпурные" клетки)

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

Однако подождите! Каждая клетка имеет свой цвет, и каждый цвет имеет различные свойства:

• Если клетка red (красная), то в неё ходить нельзя
• Если клетка pink (розовая), то в неё можно ходить
• Если клетка orange (оранжевая), то в неё можно ходить, но Беси станет пахнуть как апельсин.
• Если клетка blue (синяя) , то она содержит пираний, которые позволят Беси пройти только если она пахнет как апельсин.
• Если клетка purple (пурпурная), то Беси проскальзывает в следующую клетку в этом направлении (если только в следующую клетку можно заходить). Если следующая клетка также пурпурная, Беси продолжает скользить, пока не попадёт в не пурпурную клетку или остановится перед непроходимой клеткой. Скольжение одной клетки засчитывается как один шаг. Пурпурные клетки также удаляют запах.

(Пример ниже подробнее поясняет "пурпурные" клетки)

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

Беси помогает Эльзе играть со словами. Слова берутся из банка, содержащего \(M\) различных слов, ни одно слово не является префиксом другого.

Пока банк не пустой, Беси выбирает слово из банка, удаляет его из банка, читает его Эльзе по одному символу за раз слева направо. Задача Эльзы сказать Беси, как только она уникально определит слово, после чего Беси прекращает чтение.

Беси уже решила читать слова из словаря в порядке \(w_1,w_2,\dots,w_M\). Если Эльза ответит так быстро, как это возможно, сколько символов из каждого слова прочитает Беси?

Слова заданы в сжатом формате. Сначала мы определяем \(N+1\) (\(1\le N\le 10^6\)) различных слов и затем банк слов состоит из всех этих слов, ни одно из которых не является префиксом другого. Слова определяются следующим образом:

• Изначально, 0-ое слово - пустая строка.
• Затем для каждого each \(1\le i\le N\), \(i\)-ое слово будет равно \(p_i\)-ому слову плюс дополнительный символ в конце (\(0\le p_i<i\)). Символы выбираются так, что все \(N+1\) слов различны.

**Замечание: Память на тест 512MB, в два раза больше, чем по умолчанию.**

Беси планирует бесконечное путешествие в стране с \(N\) (\(1\leq N \leq 10^5\)) городами. В каждом городе есть портал и время зацикливания \(T_i\). Все \(T_i\). являются степенями двойки и \(T_1 + \cdots + T_N \leq 10^5\). Если Вы войдёте в портал города \(i\) в день \(t\), Вы немедленно выйдете из портала в городе \(c_{i, t\bmod{T_i}}\).

У Беси есть \(Q\) (\(1\leq Q \leq 5\cdot 10^4\)) планов её путешествия, каждый из которых есть тройка чисел \((v, t, \Delta)\). В каждом плане она начинает в городе \(v\) в день \(t\). Затем она делает следующее \(\Delta\) раз. Она входит в портал текущего города, затем ждёт один день. Для каждого из её планов она хочет узнать, в каком городе она закончит путешествие.

Корова Бесси только что закончила курс графовых алгоритмов. И выполнила кодирование своего собственного графического визуализатора! В настоящее время ее визуализатор графов только способен визуализировать корневые деревья с узлами различных значений, и он может выполнять только один вид операции: слияние.

В частности, операция слияния берет любые два различных узла в дереве с один и тем же родителем и объединяет их в один узел со значением, равным максимальному значений двух объединенных узлов, а потомки — объединение всех потомков объединенных узлов (если есть).

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

Учитывая ее начальное и конечное деревья, определите последовательность операций слияния, которые могла бы выполнить Бесси. Гарантируется, что последовательность существует.

Каждый вход состоит из \(T\) (\(1\le T\le 100\)) независимых подтестов. Гарантируется, что сумма \(N\) по всем тестам не превышает \(1000\).

Имеется \(N\) пастбищ (\(2 \le N \le 2\cdot 10^5\)), соединённых \(N-1\) дорогой, так что ои образуют дерево. Перемещение по каждой дороге занимает одну секунду. В начале на каждом пастбище 0 травы, трава на \(i\)-ом пастбище растёт со скоростью \(a_i\) (\(1\le a_i\le 10^8\)) единиц в секунду. Фермер Джон вначале находится в пастбище 1 и должен удобрить траву на каждом пастбище. Если он посещает пастбище, в котором \(x\) единиц травы, он должен потратить \(x\) единиц удобрений. Удобрять требуется только при первом посещении пастбища и удобрение пастбища занимает 0 единиц времени.

Ввод содержит дополнительный параметр \(T\in \{0,1\}\).

• Если \(T=0\), ФД должен завершить путь в пастбище 1.
• Если \(T=1\), ФД может завершить путь в любом пастбище.

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

Каждая вершина \(i\) в этом дереве ассоциируется с породой, имеющей целое число пятен \(s_i\). Дисбалансом такого дерева называется максимум \(|s_i-s_j|\) по всем парам \((i,j)\) таким, что \(j\) есть предок \(i\).

Фермер Джон не знает точное значение \(s_i\) для каждой породы, но он знает нижнюю и верхнюю границу этих величин. Ваша задача - назначить значения \(s_i \in [l_i,r_i]\) (\(0\le l_i\le r_i\le 10^9\)) каждой вершине так, чтобы минимизировать дисбаланс этого дерева.

\(i\)-ая корова размещена в точке \((x_i,y_i)\), где \(0 \leq x_i \leq 10^6\) \(0 \leq y_i \leq 10\). Стоимость построения коммуникационной линии между коровами \(i\) и \(j\) есть квадрат расстояния между ними: \((x_i-x_j)^2 + (y_i-y_j)^2\).

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

**Замечание : Лимитна время на тест = 4s, в дфа раза больше обычного..**

Сейчас Эльза создаёт новый неориентированный граф \(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\).