Деревья

ID 62562. Кластеры роботов - 2

На производстве расположены \(n\) роботов, пронумерованных от \(1\) до \(n\). Любая пара роботов может быть либо соединена проводом, либо нет. Известно, что \(i\)-й робот соединен с \(k_i\) другими роботами с номерами \(v_{i,1}, \ldots, v_{i,k_i}\). Провода двухсторонние, то есть если \(i\) связан с \(j\), то \(j\) связан с \(i\) (иными словами, \((i, j)\) и \((j, i)\) — это один и тот же провод).

Вы находитесь рядом с роботом номер \(n\). Роботом номер \(t\) можно управлять, если он связан с \(n\)-м некоторой цепочкой проводов, то есть

• либо если \(t = n\);

• либо если существуют такие \(i_1, \ldots, i_k\), что \(i_1 = n\), \(i_k = t\), и любые два соседних в этой последовательности робота \(i_j\) и \(i_{j + 1}\) связаны проводом.

Любому из роботов, которыми можно управлять, можно послать команду <<извлеки второй конец подключенного к себе провода и подключи его к другому роботу>>. Иными словами, если роботом номер \(t\) можно управлять, и есть провод, соединяющий его с роботом номер \(x\), то можно заменить провод \((t, x)\) на провод \((t, y)\) для любого \(y \neq t\), еще не связанного проводом с \(t\). Обратите внимание, что после этого вы можете потерять управление над \(t\)-м роботом, если единственная связь \(t\)-го с \(n\)-м проходила через \(x\)-й.

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

Формат входных данных
В первой строке записано целое число \(T\) (\(1 \le T \le 1000\)) — количество наборов входных данных в тесте.

Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \leq n \leq 10^5\)) — количество роботов.

Затем следуют \(n\) строк, в \(i\)-й из которых записаны числа \(k_i\) (\(0 \le k_i \le n - 1\)) и \(v_{i,1}, \ldots, v_{i,k_i}\) (\(1 \le v_{i,j} \le n\); \(v_{i,j} \neq i\)) — количество проводов, подключенных к \(i\)-му роботу, и номера роботов на противоположных концах этих проводов. Гарантируется, что данные корректны: никакие два провода не соединяют одну и ту же пару роботов, и если \(j \in v_i\), то \(i \in v_j\).

Также гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\) и сумма количества проводов по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

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

В следующих \(k\) строках выведите сами описания действий в формате <<\(y\) + \(t\) - \(x\)>> (\(1 \leq t, x, y \leq n\); \(x \neq y\)). Каждая такая строка соответствует замене провода \((t, x)\) на провод \((t, y)\).

Если возможных ответов несколько, выведите любой. Обратите внимание, что \(k\) при этом обязано быть наименьшим, при котором можно подключить максимальное количество роботов.

ID 62485. Кластеры роботов

На производстве расположены \(n\) роботов, пронумерованных от \(1\) до \(n\). Любая пара роботов может быть либо соединена проводом, либо нет. Всего на производстве \(m\) проводов и \(i\)-й из них сейчас соединяет роботов с номерами \(a_i\) и \(b_i\).

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

• либо если \(t = 1\);

• либо если существуют такие \(i_1, \ldots, i_k\), что \(i_1 = 1\), \(i_k = t\), и любые два соседних в этой последовательности робота \(i_j\) и \(i_{j + 1}\) связаны проводом.

Любому из роботов, которыми можно управлять, можно послать команду <<извлеки второй конец подключенного к себе провода и подключи его к другому роботу>>. Иными словами, если роботом номер \(t\) можно управлять, и есть провод, соединяющий его с роботом номер \(x\), то можно заменить провод \((t, x)\) на провод \((t, y)\) для любого \(y \neq t\), еще не связанного проводом с \(t\). Обратите внимание, что после этого вы можете потерять управление над \(t\)-м роботом, если единственная связь \(t\)-го с первым проходила через \(x\)-й.

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

Формат входных данных
В первой строке записано целое число \(T\) (\(1 \le T \le 1000\)) — количество наборов входных данных в тесте.

Первая строка каждого набора входных данных содержит целые числа \(n\) и \(m\) (\(1 \leq n \leq 10^5\); \(0 \leq m \leq 1.5 \cdot 10^5\)) — количество роботов и количество проводов, соответственно.

В следующих \(m\) строках дано описание проводов: в \(i\)-й строке даны целые числа \(a_i\) и \(b_i\) (\(1 \leq a_i, b_i \leq n\); \(a_i \neq b_i\)) — номера роботов, соединенных \(i\)-м проводом. Гарантируется, что никакие два провода не соединяют одну и ту же пару роботов.

Также гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\) и сумма \(m\) по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

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

В следующих \(k\) строках выведите сами описания действий по одному на каждой строке. Описание действия должно состоять из трех целых чисел \(t\), \(x\) и \(y\) (\(1 \leq t, x, y \leq n\); \(x \neq y\)), означающих, что робот номер \(t\) меняет провод \((t, x)\) на провод \((t, y)\).

Если возможных ответов несколько, выведите любой. Обратите внимание, что \(k\) при этом обязано быть наименьшим, при котором можно подключить максимальное количество роботов.

ID 60878. Гигантский дракон

Канеки смотрит на неориентированный граф на плоскости из \(n\) вершин и \(m\) ребер. В этом графе ему интересно найти самого большого дракона.

Назовем сегментом дракона три ребра графа \(AL\), \(AB\) и \(AR\), имеющие общую вершину \(A\), и обладающие следующими свойствами:

• \(0 < \measuredangle (BAL) < 45^\circ\) и направление поворота от \(\overrightarrow{AB}\) к \(\overrightarrow{AL}\) — по часовой стрелке;

• \(0 < \measuredangle (BAR) < 45^\circ\) и направление поворота от \(\overrightarrow{AB}\) к \(\overrightarrow{AR}\) — против часовой стрелки;

• \(|AB| \geqslant |AL|\) и \(|AB| \geqslant |AR|\), то есть \(AB\) — максимальное по длине из трех ребер.

При выполнении всех указанных условий вершины \(A\) и \(B\) называются началом и концом сегмента, а ребра \(AL\), \(AB\) и \(AR\) — левой лапой, основанием и правой лапой сегмента, соответственно.

Определим дракона как последовательность сегментов, в которой

• начало первого сегмента \(A_1\), также называемое головой дракона, находится в вершине \(S\);

• \(A_{i} = B_{i-1}\) для всех \(i > 1\), то есть начало каждого следующего сегмента совпадает с концом предыдущего;

• \(\left|\measuredangle \left(\overrightarrow{A_{i-1} B_{i-1}}, \overrightarrow{A_i B_i}\right)\right| < 45^\circ\), то есть угол между векторами оснований соседних сегментов строго меньше \(45^\circ\);

• \(\left|\measuredangle \left(\overrightarrow{A_1 A_i}, \overrightarrow{A_i B_i}\right)\right| < 45^\circ\), то есть угол между вектором от головы дракона \(A_1\) до начала сегмента и основанием сегмента строго меньше \(45^\circ\).

Обратите внимание, что здесь углы взяты по модулю, то есть каждый следующий сегмент может быть повернут относительно предыдущего на менее чем \(45^\circ\) как по, так и против часовой стрелки.

Мощностью дракона будем считать сумму квадратов длин оснований его сегментов, то есть \(\sum |A_i B_i|^2\). В заданном графе помогите Канеки найти дракона максимальной мощности с головой в вершине \(S\).

Формат входных данных
В первой строке входных данных даны три числа \(n, m, S\) (\(2 \leqslant n \leqslant 2\cdot 10^5\); \(1 \leqslant m \leqslant 4\cdot 10^5\); \(1 \leqslant S \leqslant n\)) — количество вершин и ребер в заданном графе и номер вершины, являющейся головой дракона.

В следующих \(n\) строках дано описание вершин графа. Каждая строка содержит два целых числа \(x_i\) и \(y_i\) — координаты \(i\)-й вершины (\(0 \leqslant x_i, y_i \leqslant 10^9\)). Гарантируется, что все вершины графа различны, то есть не существует двух вершин, обе координаты которых совпадают.

Далее следует пустая строка.

В следующих \(m\) строках дано описание ребер графа. Каждая строка содержит два целых числа \(u_i\) и \(v_i\) — номера вершин, соединенных \(i\)-м ребром (\(1 \leqslant u_i, v_i \leqslant n\); \(u_i \neq v_i\)). Гарантируется, что граф не содержит кратных ребер.

Формат выходных данных
В первой строке выходных данных выведите два числа \(k\) и \(ans\) — количество сегментов в драконе, имеющем максимальную мощность, и само значение его мощности.

В следующих \(k\) строках выведите описание сегментов в том порядке, в котором они образуют дракона. В качестве описания сегмента \(i\) выведите номера вершин \(L_i\), \(B_i\) и \(R_i\).

Будем считать, что дракон может состоять только из вершины \(S\). В таком случае количество сегментов и его мощность следует считать нулями.

Замечание
Графы, данные в первом, втором и третьем тесте условий, выглядят следующим образом.

• В первом тесте в качестве максимального дракона можно взять весь граф целиком;

• Во втором тесте ни одна тройка ребер не может быть взята в сегмент, так как не выполняется одно из обязательных условий;

• В третьем тесте максимальный дракон состоит из двух сегментов с основаниями \(9 \to 5\) и \(5 \to 1\) с лапами \((9 \to 8, 9 \to 7)\) и \((5 \to 3, 5 \to 2\)).

ID 55505. Мосты

Одна сказочная страна располагалась в дельте далекой реки ( far away river ).

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

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

Входные данные
Первая строка входных данных содержит 4 числа n, k, sh и sc — число городов, число мостов, которым можно построить, скорость лошади и скорость экипажа в метрах в секунду (1 ≤ k < n≤ 10 000, 1 ≤sh; sc·≤ 100 000). Каждая из следующих n – 1 строк содержит три целых числа b_i, e_i — номера соединяемых городов и длину дороги в метрах l_i (1 ≤ l_i ≤ 10⁶). Города пронумерованы от 1 до n, дороги пронумерованы от 1 до n – 1.

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

ID 53270. Дано дерево

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

Каждая вершина может быть покрашена в один из \(c\) цветов или быть бесцветной. Изначально все вершины бесцветные.

Вам необходимо обрабатывать два типа запросов:

1. color(\(u\), \(x\)) Дана вершина \(u\), покрасить вершину \(u\) в цвет \(x\), а затем вызвать color(\(L\), \((x + 1) \bmod c\)) для ее левого сына \(L\) и color(\(R\), \((x - 1 + c) \bmod c\)) для её правого сына \(R\). Заметим, что эта операция перекрашивает все (бесконечное) множество вершин в поддереве вершины \(u\). Здесь \(\bmod\) — операция взятия числа по модулю. Если вершина уже была покрашена, то её цвет меняется на новый.

2. Дана вершина, вывести её текущий цвет.

Формат входных данных
В первой строке вводятся два числа \(q\), \(c\) — количество запросов и цветов, соответственно (\(1 \leq q \leq 5 \cdot 10^5\), \(1 \leq c \leq 10^9\)). Затем следует \(q\) запросов, каждый из которых начинается с целого числа \(t_i\) — типа \(i\)-го запроса.

Если \(t_i\) = 1, то далее в строке даётся целое число \(x\) (\(0 \leq x \leq c - 1\)) цвет, в который надо покрасить вершину запроса \(u\). В следующей строке описан путь до вершины \(u\) в виде непустой строки \(s_i\), состоящей из символов <<L>> и <<R>>. Данная строка задаёт путь от корня дерева до вершины \(u\), где <<L>> обозначает переход к левому сыну, а <<R>> "— к правому.

Если \(t_i\) = 2, то в следующей строке задаётся путь до вершины, цвет которой необходимо вывести, заданный аналогично предыдущему запросу.

Гарантируется, что сумма длин путей до всех вершин запросов не превосходит \(5 \cdot 10^5\).

Формат входных данных
Для каждого запроса второго типа в новой строке необходимо вывести ответ на него. Если вершина бесцветная, необходимо вывести число \(-1\).

ID 45000. Вычисление выражения с вычислениями

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются целые числа, знаки арифметических операций, круглые скобки, вызовы функций ( sin , cos , abs , sqrt ) и имена переменных (только однобуквенные). Результат операции деления – вещественное число.

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

<имя переменной>=<значение>

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

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

Примеры

cos(z+abs(sqrt(r*sin(x+4))))
r=5
z=10
x=3

0.729

ID 44999. Вычисление выражения с функциями

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются целые числа, знаки арифметических операций, круглые скобки и вызовы функций ( sin , cos , abs , sqrt ). Результат операции деления – вещественное число.

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

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

Примеры

12+cos(sqrt(12+sin(2)))

11.100

ID 44998. Вычисление простого выражения со скобками

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются только целые числа, знаки арифметических операций (+-*/) и скобки произвольной вложенности. Результат операции деления – целое число.

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

Программа должна вывести значение переданного ей выражения как целое число.

Примеры

(5+20)*(98-34)/(5*8-23)

94

ID 44997. Вычисление простого выражения

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются только целые числа и знаки арифметических операций (+-*/). Результат операции деления – целое число.

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

Программа должна вывести значение переданного ей выражения как целое число.

Примеры

125-6-73/5*8

7

ID 44992. Range Minimum Query

Компания Giggle открывает свой новый офис в Судиславле, и вы приглашены на собеседование. Ваша задача — решить поставленную задачу.

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

• запрос: «? i j» — возвращает минимальный элемент между i-ым и j-м, включительно;
• изменение: «+ i x» — добавить элемент x после i-го элемента списка. Если i=0, то элемент добавляется в начало массива.

Конечно, эта структура должна быть достаточно хорошей.

Первая строка входного файла содержит единственное целое число n — число операций над массивом (1<=n<=200000). Следующие n строк описывают сами операции. Все операции добавления являются корректными. Все числа, хранящиеся в массиве, по модулю не превосходят 10⁹.

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

Комментарий к примеру тестов

Примеры

8
+ 0 5
+ 1 3
+ 1 4
? 1 2
+ 0 2
? 2 4
+ 4 1
? 3 5

4
3
1

ID 44989. Переворот

Дан массив. Надо научиться обрабатывать два типа запросов.

* 1 L R - перевернуть отрезок [L,R]

* 2 L R - найти минимум на отрезке [L,R]

Первая строка файла содержит два числа n, m. (1<=n,m<=10⁵) Во второй строке находится n чисел ni (1<=a_i<=10⁹) - исходный массив. Остальные m строк содержат запросы, в формате описанном в условии. Для чисел L, R выполняется ограничение (1<=L<=R<=n).

На каждый запрос типа 2, во входной файл выведите ответ на него, в отдельной строке.

Примеры

10 7
5 3 2 3 12 6 7 5 10 12
2 4 9
1 4 6
2 1 8
1 1 8
1 8 9
2 1 7
2 3 6

3
2
2
2

ID 44987. Бинарное дерево (вставка, поиск, удаление)

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

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

DELETE n — если указанное число есть в дереве, удалять его и выводить слово «DONE», если нет — оставлять дерево как было и выводить слово «CANNOT». При удалении элемента, имеющего два сына, обязательно обменивать значение с максимальным элементом левого поддерева.

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

В каждой строке входных данных записан один из запросов ADD n или DELETE n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

Для каждого запроса выводите ответ на него. Для запросов ADD, DELETE и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:

template void print_tree(Node *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i < level; i++)

    cout << ".";

  cout <<  p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

Примеры

ADD 2
ADD 7
ADD 5
PRINTTREE
ADD 5
DELETE 3
ADD 0
PRINTTREE
DELETE 7
PRINTTREE

DONE
DONE
DONE
2
..5
.7
ALREADY
CANNOT
DONE
.0
2
..5
.7
DONE
.0
2
.5

ID 44985. Бинарное дерево (вставка, поиск)

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

ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».

SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.

PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.

В каждой строке входных данных записан один из запросов ADD n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.

Для каждого запроса выводите ответ на него. Для запросов ADD и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:
 

template void print_tree(Node *p, int level)

{

  if(p==NULL)

    return;

  print_tree(p->left, level+1);

  for(int i=0; i < level; i++)

    cout << ".";

  cout <<  p->data << endl;

  print_tree(p->right, level+1);

}

(Изначальный вызов этой функции — print_tree(root,0).)

Примеры

ADD 2
ADD 3
ADD 2
SEARCH 2
ADD 5
PRINTTREE
SEARCH 7

DONE
DONE
ALREADY
YES
DONE
2
.3
..5
NO

ID 44774. Ветки дерева

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

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

Выведите список требуемых вершин.

 

Примеры

7 3 2 1 9 5 4 6 8 0

2
9

ID 44773. Обход дерева

Выведите все элементы полученного дерева в порядке возрастания.

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

Выведите ответ на задачу.

Примеры

7 3 2 1 9 5 4 6 8 0

1
2
3
4
5
6
7
8
9

ID 44772. Второй максимум в дереве

Выведите второй по величине элемент в построенном дереве. Гарантируется, что такой найдется.

Дана последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.

Выведите ответ на задачу.

Примеры

7 3 2 1 9 5 4 6 8 0

8

ID 44649. Сбалансированность

Примеры

7 3 2 1 9 5 4 6 8 0

YES

ID 44648. Выведи развилки

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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. Постройте по этой последовательности дерево.

Выведите ответ задачи.

Примеры

7 3 2 1 9 5 4 6 8 0

3
5
7

ID 44647. Выведи листья

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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.

Выведите ответ на задачу.

Примеры

7 3 2 1 9 5 4 6 8 0

1
4
6
8

ID 44646. Количество элементов в дереве

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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.

Выведите ответ на задачу.

Примеры

7 3 2 1 9 5 4 6 8 0

9