--->
16 задач
<---
Источники
ограничение по времени на тест
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
#112599
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:
- Закрасить клетку (i,j) в черный цвет.
- Для клетки (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
#113550
Темы:
[Динамическое программирование]
[Дерево отрезков, RSQ, RMQ]
[Система непересекающихся множеств]
[Разреженные таблицы (sparse table)]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2017,
2 день,
Антивещество
]
ограничение по времени на тест
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
#113557
ограничение по времени на тест
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
#113575
ограничение по времени на тест
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
Выбрано
:
|