Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Реализуйте систему непересекающихся множеств. Вместе с каждым множеством храните минимальный, максимальный элемент в этом множестве и их количество.
Первая строка входного файла содержит n — количество элементов в носителе (1 ≤ n ≤ 300 000). Далее операций с множеством. Операция get должна возвращать минимальный, максимальный элемент в соответствующем множестве, а также их количество.
Выведите последовательно результат выполнения всех операций get.
Входные данные
5
union 1 2
get 3
get 2
union 2 3
get 2
union 1 3
get 5
union 4 5
get 5
union 4 1
get 5
Выходные данные
3 3 1
1 2 2
1 3 3
5 5 1
4 5 2
1 5 5
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 64 мегабайта
ввод: стандартный ввод
вывод: стандартный вывод
В очередной онлайн игре игроки, как обычно, сражаются с монстрами и набирают опыт. Для того, чтобы сражаться с монстрами, они объединяются в кланы. После победы над монстром, всем участникам клана, победившего его, добавляется одинаковое число единиц опыта. Особенностью этой игры является то, что кланы никогда не распадаются и из клана нельзя выйти. Единственная доступная операция — объединение двух кланов в один.
Поскольку игроков стало уже много, вам поручили написать систему учета текущего опыта игроков.
В первой строке входного файла содержатся числа n (1 ≤ n ≤ 200000) и m (1 ≤ m ≤ 200000) — число зарегистрированных игроков и число запросов.
В следующих m строках содержатся описания запросов. Запросы бывают трех типов:
- join X Y — объединить кланы, в которые входят игроки X и Y (если они уже в одном клане, то ничего не меняется).
- add X V — добавить V единиц опыта всем участникам клана, в который входит игрок X (1 ≤ V ≤ 100).
- get X — вывести текущий опыт игрока X.
Изначально у всех игроков 0 опыта и каждый из них состоит в клане, состоящим из него одного.
Для каждого запроса get X выведите текущий опыт игрока X.
Входные данные
3 6
add 1 100
join 1 3
add 1 50
get 1
get 2
get 3
Выходные данные
150
0
50
Ограничение по времени на тест: 4 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Даны точки на плоскости, являющиеся вершинами полного графа. Вес ребра равен расстоянию между точками, соответствующими концам этого ребра. Требуется в этом графе найти остовное дерево минимального веса.
Первая строка входного файла содержит натуральное число n — количество вершин графа (1≤ n ≤10000). Каждая из следующих n строк содержит два целых числа xi, yi — координаты i-й вершины (−10000≤ xi,yi ≤10000). Никакие две точки не совпадают.
Первая строка выходного файла должна содержать одно вещественное число — вес минимального остовного дерева.
Входные данные
2
0 0
1 1
Выходные данные
1.4142135624
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Требуется найти в связном графе остовное дерево минимального веса.
Первая строка входного файла содержит два натуральных числа n и m — количество вершин и ребер графа соответственно. Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами bi, ei и wi — номера концов ребра и его вес соответственно (1≤ bi,ei ≤ n , 0≤ wi ≤100000). n ≤200000, m ≤200000.
Граф является связным.
Первая строка выходного файла должна содержать одно натуральное число — вес минимального остовного дерева.
Входные данные
4 4
1 2 1
2 3 2
3 4 5
4 1 4
Выходные данные
7
Ограничение по времени на тест: 6 секунд
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Вам дан взвешенный ориентированный граф, содержащий n вершин и m рёбер. Найдите минимально возможную сумму весов n−1 ребра, которые нужно оставить в графе, чтобы из вершины с номером 1 по этим ребрам можно было добраться до любой другой вершины.
В первой строке даны два целых числа n и m (1≤ n ≤1000, 0≤ m ≤10000) — количество вершин и ребер в графе.
В следующих m строках даны ребра графа. Ребро описывается тройкой чисел ai, bi и wi (1≤ _ai,bi _≤ n ; −10^9≤ wi ≤10^9) — номер вершины, из которой исходит ребро, номер вершины, в которую входит ребро, и вес ребра.
Если нельзя оставить подмножество ребер так, чтобы из вершины с номером 1 можно было добраться до любой другой, в единственной строке выведите «NO».
Иначе, в первой строке выведите «YES», а во второй строке выведите минимальную возможную сумму весов ребер, которых необходимо оставить.
Входные данные
2 1
2 1 10
Выходные данные
NO
Входные данные
4 5
1 2 2
1 3 3
1 4 3
2 3 2
2 4 2
Выходные данные
YES
6