Темы --> Информатика --> Структуры данных --> Система непересекающихся множеств
---> 16 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

Входные данные

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

Следующие m строк задают рёбра графа; i-я из этих строк содержит два числа ui и vi (1 ≤ ui, vi ≤ 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
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:

  1. Закрасить клетку (i,j) в черный цвет.
  2. Для клетки (i,j) узнать её ближайших белых соседей по вертикали и горизонтали.

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

Входные данные

начала вводятся размеры поля N и M ( 1 ≤ N ≤ 20 , 1 ≤ M ≤ 50000 ), затем количество команд K ( 1 ≤ K ≤ 10 5 ), а затем сами команды. Команды записаны по одной в строке в следующем формате:

  • Color i j — окраска клетки ( i , j ) в черный цвет;
  • Neighbors i j — нахождение белых соседей для клетки ( i , j ). (Клекта ( i , j ) может быть как белой так и черной.)

Выходные данные

На каждый запрос Neighbors требуется вывести сначала количество ближайших белых соседей (или 0 , если ни с одной из сторон белых клеток не осталось), а затем их координаты (соседей можно перечислять в произвольном порядке). Если запросов Neighbors нет, ничего выводить не надо.

Примеры
Входные данные
5 5 10
Neighbors 3 1
Color 4 1
Color 2 4
Color 4 5
Color 2 2
Neighbors 5 4
Neighbors 5 5
Neighbors 2 4
Color 3 5
Neighbors 3 5
Выходные данные
3
2 1
4 1
3 2
3
4 4
5 3
5 5
2
3 5
5 4
4
1 4
3 4
2 3
2 5
3
2 5
5 5
3 4
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
128 megabytes

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

Известно n типов экспериментов, приводящих к получению антивещества. В результате проведения эксперимента i-го типа в выходной контейнер реактора добавляется от li до ri граммов антивещества. Из соображений безопасности запрещается накапливать в контейнере более a граммов антивещества.

Затраты на проведение эксперимента i-го типа составляют ci, а стоимость одного грамма полученного антивещества составляет 109.

Если после проведения экспериментов в контейнере образовалось t граммов антивещества, а суммарные затраты на проведение экспериментов в реакторе составили s, то прибыль определяется по формуле (t·109 - s). Компании необходимо разработать стратегию проведения экспериментов, позволяющую максимизировать прибыль, которую можно гарантированно получить.

В зависимости от результатов предыдущих экспериментов стратегия определяет, эксперимент какого типа следует провести, или решает прекратить дальнейшее выполнение экспериментов. Стратегия позволяет гарантированно получить прибыль x, если при любых результатах проведения экспериментов: во-первых, в контейнере реактора оказывается не более a граммов антивещества, во-вторых, прибыль составит не менее x.

Например, пусть возможен только один тип эксперимента, порождающий от 4 до 6 граммов антивещества, затраты на его проведение равны 10, а вместимость контейнера составляет 17 граммов. Тогда после двукратного проведения эксперимента в контейнере может оказаться от 8 до 12 граммов антивещества. Если получилось 12 граммов, то больше проводить эксперимент нельзя, так как в случае получения 6 граммов антивещества контейнер может переполниться. В остальных случаях можно провести эксперимент в третий раз и получить от 12 до 17 граммов антивещества. В худшем случае придётся провести эксперимент трижды, затратив в сумме 30, прибыль составит (12·109 - 30) = 11 999 999 970.

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

Входные данные

Первая строка входных данных содержит два целых числа: n — количество типов экспериментов и a — максимально допустимое количество антивещества в контейнере (1 ≤ n ≤ 100, 1 ≤ a ≤ 2 000 000).

Следующие n строк содержат по три целых числа li, ri и ci — минимальное и максимальное количество антивещества, получаемое в результате эксперимента типа i, и затраты на эксперимент этого типа, соответственно (1 ≤ li ≤ ri ≤ a, 1 ≤ ci ≤ 100).

Выходные данные

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

Примеры
Входные данные
1 17
4 6 10
Выходные данные
11999999970
Входные данные
2 11
2 2 100
3 5 5
Выходные данные
9999999890
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Города представлены в виде точек в двумерной системе координат. Дорога между двумя городами представлена ​​в виде отрезка, соединяющего две точки, в которых расположены города. Длина дороги равна длине отрезка в километрах.

В настоящее время страна переживает экономический спад, поэтому премьер-министр решил, что из-за отсутствия бюджета они не будут строить дороги длиннее, чем D километров. Кроме того, премьер-министр радуется мелочам, поэтому он будет счастлив, если по крайней мере в одной сети будет существовать непустое подмножество городов (оно может включать все города в сети), где общая сумма жителей делится на К . Например, если K = 4 и есть сеть с городами, в которых есть 3 , 5 , 7 жителей соответственно, премьер-министр будет счастлив, потому что сумма жителей в первых двух городах равна 8 .

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

Входные данные

Первая строка ввода содержит целые числа N и K (1 ≤ N ≤ 50000, 1 ≤ K ≤ 30) . Каждая из следующих N строк содержит три целых числа x i ; y i ; k i (0 ≤ x i , y i , k i ≤ 100000000) , которые представляют координату x города, координату y и количество жителей в этом городе, соответственно. На входных данных не будет двух городов с одинаковыми координатами. Кроме того, не будет ни одного города, в котором число жителей делится на К .

Выходные данные

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

Примечание

Объяснение первого примера: единственный способ удержать премьер-министра в счастливом настроение - все города должны находятся в одном округе. Минимальный D , для которого это возможно, равен 1.414 .

Объяснение второго примера: премьер-министр будет рад, если первые 5 городов находятся в одном округе. Если D = 5.657 , премьер-министр может соединить города 1, 2, 3, 5 с городом 4 . В этом случае сумма жителей в городах 1, 2, 3, 4, 5 составит 11 , что делится на 11 , Поэтому премьер-министр будет счастлив.

Примеры
Входные данные
3 3
0 4 4
1 5 1
2 6 1
Выходные данные
1.414
Входные данные
6 11
0 0 1
0 1 2
1 0 3
1 1 4
5 5 1
20 20 10
Выходные данные
5.657
Входные данные
6 5
20 20 9
0 0 3
0 1 1
10 0 1
10 1 6
12 0 3
Выходные данные
2.000
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Давным-давно в одной далекой-далекой галактике, было N планет. Также было N - 1 межпланетных магистралей, соединявших между собой все планеты (не обязательно напрямую). Иными словами, сеть планет и магистралей образовывала дерево. Кроме того, каждая магистраль имеет свой показатель интересности, заданный неотрицательным целым числом. Пара планет ( A , B ) называется скучной, если выполняются следующие условия:

1. A и B - различные планеты.

2. В действующей сети межпланетных магистралей существует путь между A и B .

3. Побитовый XOR показателей интересности всех магистралей в этом пути равен 0.

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

Входные данные

Первая строка содержит одно целое число N ( 1 ≤ N ≤ 100000 ). Каждая из следующих N - 1 строк содержит три целых числа A i , B i , Z i ( 1 ≤ A i , B i ≤ 100000 , 0 ≤ Z i ≤ 1000000000 ), которые означают, что планеты с номерами A i и B i соединены магистралью с показателем интересности Z i . Последняя строка содержит N - 1 число: перестановку натуральных чисел от 1 до N - 1 , отражающую порядок уничтожения магистралей (если i -е число в строке равно j , то император уничтожит дорогу между планетами A j и B j на i -м шаге).

Выходные данные

Выведите N строк, в k -й строке выведите одно число - количество пар скучных планет после уничтожения k - 1 дорог.

Примечание

Решения, работающие при N ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие в случае когда показатель интересности всех путей равен 0, будут оцениваться не менее чем в 30 баллов.

Примеры
Входные данные
2
1 2 0
1
Выходные данные
1
0
Входные данные
3
1 2 4
2 3 4
1 2
Выходные данные
1
0
0
Входные данные
4
1 2 0
2 3 0
2 4 0
3 1 2
Выходные данные
6
3
1
0

Страница: << 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест