Problem A. SST for sparse graph ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2 10
2 3 10
3 1 10

20

Задача B. Три пути ≡

Условие

Цапля вилка недавно переехала в Антарктику в государство пингвинов — Пингвинию, и устроилась работать в местную логистическую компанию. Всего в Пингвинии N городов и M дорог, по дорогам можно двигаться в обе стороны. Исторически сложилось, что каждый пингвин посещает ровно три города (возможно проезжая по пути через остальные города). Пингвины не любят однообразие, поэтому одна из самых популярных услуг в логистической компании это прокладка маршрутов между тремя городами a, b, c так чтобы при проезде из a в b, из a в c, и из b в с существовал максимум один город который посещался 3 раза.

Как вы уже могли догадаться Цапля просит вас о помощи, у неё скопилось ровно Q запросов вида a, b, c. И для каждого запроса требуется вывести 3 пути, из a в b, из a в c, и из b в c, так чтобы эти пути удовлетворяли заданным требованиям.

Формат входного файла

Входной файл содержит числа N и M. Далее следует M пар чисел u_i и v_i, означающих что города u_i и v_i соединены дорогой. Далее следует число Q, за которым следует Q попарно различных чисел a_i, b_i, c_i.

Формат выходного файла

Выходной файл должен содержать 3 × Q строк, первое число в строке k_i — количество вершин в пути, далее k_i чисел — номера вершин пути в порядке посещения.

Ограничения

3 ≤ N ≤ 1000, 1 ≤ Q ≤ 1000, 1 ≤ M ≤ N ⋅ (N − 1)2, 1 ≤ u_i, v_i ≤ N, u_i ≠ v_i, 1 ≤ a_i, b_i, c_i ≤ N

Примеры тестов

3 2
1 2
2 3
1
1 2 3

2 1 2
3 1 2 3
2 2 3

4 3
1 2
1 3
1 4
2
3 4 1
1 2 4 

3 3 1 4 
2 3 1 
2 4 1 
2 1 2 
2 1 4 
3 2 1 4 

5 6
2 3
4 5
1 2
1 3
1 4
1 5
2
2 3 4
2 3 5

2 2 3 
3 2 1 4 
4 3 2 1 4 
2 2 3 
4 2 1 4 5 
5 3 2 1 4 5 

Задача C2. Разрезание графа ≡

Условие

Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:

• cut — разрезать граф, то есть удалить из него ребро;
• ask — проверить, лежат ли две вершины графа в одной компоненте связности.

Известно, что после выполнения всех операций типа cut рёбер в графе не осталось. Найдите результат выполнения каждой из операций типа ask.

Формат входного файла

Первая строка входного файла содержит три целых числа, разделённые пробелами — количество вершин графа n, количество рёбер m и количество операций k (1 ⩽ n ⩽ 50 000, 0 ⩽ m ⩽ 100 000, m ⩽ k ⩽ 150 000).

Следующие m строк задают рёбра графа; i-ая из этих строк содержит два числа u_i и v_i (1 ⩽ u_i,  v_i ⩽ n), разделённые пробелами — номера концов i-го ребра. Вершины нумеруются с единицы; граф не содержит петель и кратных рёбер.

Далее следуют k строк, описывающих операции. Операция типа cut задаётся строкой «cut ~u v» (1 ⩽ u,  v ⩽ n), которая означает, что из графа удаляют ребро между вершинами u и v. Операция типа ask задаётся строкой «ask u v» (1 ⩽ u,  v ⩽ n), которая означает, что необходимо узнать, лежат ли в данный момент вершины u и v в одной компоненте связности. Гарантируется, что каждое ребро графа встретится в операциях типа cut ровно один раз.

Формат выходного файла

Для каждой операции ask во входном файле выведите на отдельной строке слово «YES», если две указанные вершины лежат в одной компоненте связности, и «NO» в противном случае. Порядок ответов должен соответствовать порядку операций ask во входном файле.

Ограничения

Примеры тестов

3 3 7
1 2
2 3
3 1
ask 3 3
cut 1 2
ask 1 2
cut 1 3
ask 2 1
cut 2 3
ask 3 1

YES
YES
NO
NO

Задача D. Ребра добавляются, граф растет ≡

Условие

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

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

На первой строке n — количество вершин, m — количество операций "добавить ребро". Следующие m строк содержат пары чисел от 1 до n — описание добавляемых ребер. 1 ≤ n, m ≤ 300 000.

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

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

Ограничения

Примеры тестов

3 3
1 2
2 3
3 1

110

Задача E. Число комнат в лабиринте ≡

Условие

Карта лабиринта, выступающего в качестве игрового поля, представлена в виде матрицы n × m клеток. Каждая клетка маркируется одним из двух значений: свободное пространство либо непроходимый участок. Полагается, что в процессе игры персонаж может передвигаться в одном из четырех направлений: вверх, вниз, вправо и влево, всегда при этом оставаясь в свободных клетках.

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

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

Формат входного файла

Во входном файле "input.txt" построчно хранится двумерный массив символов, представляющий собой карту лабиринта. Свободные клетки в нем обозначаются пробелами (ASCII 32), в то время как все остальные выступают в качестве непроходимых участков.

Формат выходного файла

Выходной файл "output.txt" должен содержать полученное число комнат.

Ограничения

0 < (n, m) ≤ 5000

Примеры тестов

xxxxxxxxx    xxx xx xxxxxxxxxxxx
xxxxxxxxx    xxx xx xxxxxxxxxxxx
xxxxxxxxx    xxx                
xxxxxxxxx    xxxxxxxxx   xxxxxxx
xxx          xxxxxxxxx   xxxxxxx
xxx   xxx    xxxxxxxxx          
xxx          xxxxxxxxx          
xxxxxx  xxx  xxxxxxxxx   xxxxxxx
xxxxxx  xxx  xxxxxxxxx   xxxxxxx
xxxxxx                   xxxxxxx
xxxxxxxxxxxxx            xxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

1

xxx   xxx       xxxx  0000000000
xxx   xxx   xx  xxxx  0000000000
xxx   xxx   xx                  
xxxxxxxxx   xxxxxxxx  aaa    iii
            xxxxxxxx  aaa       
xxx   xxx   xxaa    aa    000iii
              aa    aa    000iii
iiiiii   aaa  aaaaaaaa    000iii
iiiiii   aaa  aaaaaaaa    000iii
000iii                          
000000   000  00000000    000000
000000   0000000000000    000000

3

Задача F. Ещё одна задача про деревья ≡

Условие

Есть граф из N вершин. Изначально он пустой. Нужно обработать M запросов:

1. добавить ребро из вершины v₁ в вершину v₂, при этом вершины v₁ и v₂ находятся в разных деревьях и вершина v₂ является корнем какого-то дерева.
2. по двум вершинам a и b определить, лежат ли они в одном дереве.

Решение задачи: реализуем СНМ с эвристикой сжатия путей:

int n, m, l[NMAX];

int calc_leader (int v)
{
	if (l[v] != v)
		l[v] = calc_leader (l[v]);
	return l[v];
}

int main()
{
	scanf ("%d%d", & n, &m);
	for (int i = 1; i <= n; i ++)
		l[i] = i;
	for (int i = 1; i <= m; i ++)
	{
		int x, y, z;
		scanf ("%d%d%d", &z, &x, &y);
		if (z == 1)
			l[y] = x;
		else
		if (calc_leader (x) == calc_leader (y))
			printf ("YES\n");
		else
			printf ("NO\n");
	}
}

Вам же предстоит сделать тест, на котором это решение будет работать долго. Более точно, нужно сделать тест, на котором количество вызовов функции calc_leader будет не меньше, чем 14Mlog₂M.

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

Входной файл содержит два целых числа N и M (1 ≤ N ≤ 10⁶, 1 ≤ M ≤ 10⁵, M ≤ N).

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

Выведите M строк. i-ая строка должна иметь вид 1 x y, если i-ый запрос заключается в добавлении ребра из вершины x в вершину y, или 0 x y, если спрашивается, лежат ли вершины x и y в одном дереве.

Ограничения

Примеры тестов

2 2

1 1 2
0 1 2