#113703

Раскраска графа

Темы: [Динамика по подмножествам] [Динамическое программирование]

Дан граф из $n$ вершин, раскрасьте его в минимально возможное число цветов так, чтобы никакие две вершины, соединенные ребром, не были одного цвета.

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

В первой строке содержится число $t$ - количество тестовых примеров ($1 \leq t \leq 5$).

Далее содержится $t$ тестовых случаев, заданных в следующем формате:

В первой строке записаны числа $n$ и $m$ - количество вершин и ребер соответственно ($1 \leq n \leq 17$, $0 \leq m \leq \frac{n \cdot (n - 1)}{2}$).

Затем идет $m$ строк, в которых содержится по два числа $v_i$ $u_i$, что означает, что вершины $v_i$ и $u_i$ соеденены ребром ($1 \leq v_i, u_i \leq n, v_i \neq u_i$).

Гарантируется, что все ребра в каждом тестовом случае различны.

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

Для каждого тестового случая в первой строке выведите минимальное число цветов $k$.

Во второй строке выведите $n$ чисел $a_i$ - цвета вершин ($1 \leq a_i \leq k$).

Примеры

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

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

3
3 2 1
2
1 2 2 1 1
3
1 3 1 1 2 1

#113704

Thorny Graph

Темы: [Точки сочленения] [Компоненты сильной связности]

Как гласят старые малоярославские легенды, где-то далеко-далеко, где сборная России когда-то готовилась к международной олимпиаде, в одной из общеобразовательных школ живёт Граф. Ориентированность Графа, как следует из легенд, меняется от дня ко дню вместе с количеством вершин и ребер, что позволяет Графине и её отражению не скучать и играть во множество игр на Графе.

Вот уже многие дни Граф обрёл постоянную ориентированность; однако в последнее время Граф часто стал бывать раздражительным и колючим, и для Графини настали нелёгкие дни. Чтобы хоть как-то облегчить себе жизнь, Графиня решила написать программу, которая по текущему состоянию, то есть набору вершин и рёбер, сообщит Графине, является ли граф колючим. По опыту прошлых дней, Графиня заключила, что Граф является колючим, если и только если через любое его ребро проходит не более чем один простой цикл.

Напомним, что последовательность ребер ( u ₁ , u ₂ ) , ( u ₂ , u ₃ ) , ..., ( u _{k

- 1} , u _k ) , ( u _k , u ₁ ) является простым циклом, если вершины u ₁ , u ₂ , ..., u _k попарно различны. Простой цикл проходит через ребро e , если ребро e содержится в последовательности ребер цикла.

Петлёй в графе называется ребро ( u , v ) , т.ч. u = v .

Рёбра ( u ₁ , v ₁ ) и ( u ₂ , v ₂ ) называются кратными, если u ₁ = u ₂ и v ₁ = v ₂ .

Помогите Графине понять, является ли её Граф, являющийся ориентированным графом без петель и кратных ребер, колючим или нет.

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

В первой строке записаны целые неотрицательные числа n и m ( 1 ≤ n ≤ 500 000 , 0 ≤ m ≤ 10 ⁶ - количество вершин и рёбер графа-Графа.

Далее в следующих m строках записано по паре целых чисел u , v , 1 ≤ u , v ≤ n , u ≠ v .

Гарантируется, что в Графе не существует петель и кратных ребер.

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

Выведите слово " YES ", если Граф является колючим, и " NO " иначе.

Примеры

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

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

YES

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

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

NO

#113705

Крыса - роботяга

Темы: [Дерево отрезков, RSQ, RMQ] [Хеш] [Бор] [Сканирующая прямая]

Компания « Rapid City Dynamics » знаменита её роботами-собаками, роботами-гепардами и даже человекоподобными роботами. Но большие проекты требуют больших денег, так что компания решила создать что-то простое, но популярное (и более востребованное). Так что компания разрабатывает нового робота « Rat-O-Matic », и вы, как работник « Rapid City Dynamics », принимаете участие в этом.

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

Есть ровно n рамок. Каждая рамка задана тремя числами: x , y и r . Она задаёт территорию, ограниченую между двух квадратов со сторонами параллельным осям координат и центрами в точке ( x , y ): радиус первого квадрата r , а второго — 2· r . Радиус квадрата — это расстояние между его центром и стороной. Ко всему прочему, каждой рамке соответствует своя нота. Сейчас есть только 3 возможных ноты, обозначим их как « r », « a » и « t ».

Гарантируется, что никакие две рамки не касаются и не пересекаются.

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

Известно, что людям нравятся похожие мелодии. В вашей базе данных имеются m мелодий. Каждая мелодия задаётся строкой из символов, которая задаёт ноты. Мелодия, сгенерированная крысой, содержится в мелодии из базы данных, если она содержится в ней в качестве подстроки. Популярность сгенерированной мелодии - это число мелодий в базе данных, которые содержат её. Одинаковые мелодии из базы данных должны быть учтены несколько раз.

В попытке создания самого классного расположения рамок, вы совершили q экспериментов. Эксперименты бывают трёх типов:

Выключить рамку x . Гарантируется, что рамка была включена до этой операции. Выключенные рамки не влияют на мелодию крысы. Вначале все рамки включены.
Включить рамку x . Гарантируется, что рамка была выключена до этой операции.
Посчитать популярность мелодии, сгенерированной роботом при движении от точки с координатами ( 10 ⁹ , 10 ⁹ ) до рамки x . Гарантируется, что рамка x является включённой.

Твоя задача — провести эти эксперименты, используя только свой компьютер!

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

В первой строке содержится натуральное число n — количество рамок ( 1 ≤ n ≤ 2·10 ⁵ ).

В следующих n строках описаны рамки, i -я из них содержит три натуральных числа x _i , y _i , r _i и символ c _i , разделённые пробелами ( - 10 ⁸ ≤ x _i , y _i ≤ 10 ⁸ , 1 ≤ r _i ≤ 10 ⁸ , и c _i $\text{[math]}$ {« r », « a », « t »} — координаты центра рамки, радиус внутреннего квадрата и её нота, соответственно.

Следующая строка содержит натуральное число m — количество мелодий в базе ( 1 ≤ m ≤ 2·10 ⁵ ).

Следующие m строк содержат непустые строки из букв « r », « a » или « t », которые задают мелодии. Суммарная длина всех строк не превосходит 2·10 ⁵ .

Следующая строка содержит натуральное число q — количество экспериментов ( 1 ≤ q ≤ 2·10 ⁵ ).

Следующие q строк описывают эксперименты, j -я из них содержит символ t _j (« - », « + » или « ? ») и натуральное число x _j отделённое пробелом. Символ задаёт тип эксперимента (« - » — 1, « + » — 2 и « ? » — 3), а число обозначает номер рамки.

Гарантируется, что есть хотя бы один эксперимент третьего типа.

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

Для каждого эксперимента третьего типа, выведите одно число — популярность получившейся мелодии.

Группы тестов (Все группы независимы)

10 баллов — (1 ≤ n, m, q ≤ 100, суммарная длина строк не превосходит 100, тесты 2-6) .

10 баллов — ( 1 ≤ n ≤ 4 000, 1 ≤ m, q ≤ 100, суммарная длина строк не превосходит 100, тесты 7-9) .

10 баллов — ( 1 ≤ n, q ≤ 100, 1 ≤ m ≤ 200 000 , суммарная длина строк не превосходит 200 000, тесты 10-13) .

10 баллов — ( 1 ≤ n ≤ 4 000, 1 ≤ m ≤ 200 000, 1 ≤ q ≤ 100, суммарная длина строк не превосходит 200 000, тесты 14-16) .

10 баллов — ( 1 ≤ n ≤ 200 000, 1 ≤ m, q ≤ 100, суммарная длина строк не превосходит 100, тесты 17-19) .

15 баллов — ( 1 ≤ n, q ≤ 200 000, 1 ≤ m ≤ 100, суммарная длина строк не превосходит 100, тесты 20-23) .

35 баллов — полные ограничения, тесты 24-57.

Примеры

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

3
3 3 4 r
2 4 1 a
14 4 1 t
3
rat
rara
aaa
6
? 3
? 2
- 1
? 2
+ 1
? 2

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

#113706

Почтовая реформа

Темы: [Деревья] [Дерево отрезков, RSQ, RMQ]

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

Недавно образованное почтовое агентство «Экс-Федя» предлагает уникальную услугу — коллективную посылку. Эта услуга позволяет отправлять посылки жителям всех городов на каком-либо пути по цене обычной посылки. Удивительно, но пользоваться такой услугой стали только волшебники Флатландии, которые стали в большом количестве отправлять друг другу магические кактусы. Агентство столкнулось с непредвиденной проблемой: как известно, все волшебники живут в башнях и мало того, что не строят в них лестницы, так еще время от времени меняют их высоту. Поэтому, чтобы доставить посылку волшебнику, который живет в башне высотой h , курьеру агентства требуется иметь с собой не менее h метров веревки.

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

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

Первая строка входного файла содержит число n — количество городов в Флатландии ( 1 ≤ n ≤ 50 000 ). Во второй строке находится n положительных чисел, не превосходящих 10 ⁵ — высоты башен в городах. В следующих n - 1 строках содержится по два числа u _i и v _i — описание i -й дороги, 1 ≤ u _i , v _i ≤ n , u _i ≠ v _i . В следующий строке содержится число k — количество запросов ( 1 ≤ k ≤ 100 000 ). В следующих k строках содержатся описания запросов в следующем формате:

Уведомление от волшебника из города i о том, что высота его башни стала равна h , имеет вид ! i h , 1 ≤ i ≤ n , 1 ≤ h ≤ 10 ⁵ .
Запрос от курьера о выдаче веревки для доставки посылок во все города на пути от i до j включительно имеет вид ? i j , 1 ≤ i , j ≤ n .

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

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

Группы тестов (Все группы независимы)

20 баллов — ( 1 ≤ n, k ≤ 100) .

30 баллов — каждый город соединен дорогами не более чем с двумя другими.

50 баллов — полные ограничения.

Примеры

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

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

3
3
5

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

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

1
1000

#113707

Симпатичные прямоугольники наносят ответный удар

Темы: [Хеш] ["Два указателя"]

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

Картина представляет собой прямоугольник N на M сантиметров, разделенный на маленькие квадратики 1 на 1 сантиметр со сторонами, параллельными сторонам картины. Для достижения гармонии каждый из этих квадратиков Вася покрасил одним из 26 особых цветов, обозначаемых маленькими латинскими буквами.

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

abc
acb

симпатичными являются все части, состоящие из одного квадратика (их 6), а также части

bc a

cb и a

Напишите программу, которая по информации о шедевре Васи определит его стоимость.

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

В первой строке содержатся два числа N и M ( 1 ≤ N , M ≤ 300 ). В следующих N строках идут строки, состоящие из M маленьких латинских символов. Символ в i -й строке j -м столбце определяет цвет соответствующего квадратика картины.

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

Выведите стоимость шедевра — количество частей, симметричных относительно своего центра.

Система оценки

n, m < 10 -> 20 баллов

n, m < 50 -> 30 баллов

n, m < 100 -> 20 баллов

n, m < 300 -> 30 баллов

Примечание

Этот пример разобран в условии

Симпатичными являются шесть частей 1 × 1 , одна часть 1 × 2 и сама картина.

Примеры

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

2 3
abc
acb

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

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

3 2
ab
cc
ba

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