| Codeforces Round 1071 (Div. 3) |
|---|
| Закончено |
Это задача с двойным запуском (коммуникационная).
Есть два игрока: Игрок A (Агент) и Игрок B (Blackslex ). Жюри сначала взаимодействует с игроком A. После того как игрок A завершит свое взаимодействие, жюри будет взаимодействовать с игроком B. Обратите внимание, что игрок A и игрок B не могут напрямую передавать информацию друг другу; оба игрока могут только отправлять информацию или получать информацию от жюри, но они могут согласовать стратегию, которую будут использовать для общения.
Пингвинья Республика — это двудольный связный неориентированный граф $$$G$$$ с $$$n$$$ вершинами и $$$m$$$ ребрами. Blackslex собирается провести запрещенные полевые исследования на вершине $$$1$$$. Из-за ограничений на передвижение его высадят на неизвестной вершине $$$v$$$ ($$$2 \leq v \leq n$$$). Ему нужно добраться до вершины $$$1$$$, не имея информации о графе.
Для своего путешествия он подкупил пингвиньего агента и согласовал некоторую стратегию общения, используя следующий метод: агент будет незаметно окрашивать каждую вершину в один из трех цветов: красный, зеленый или синий. С точки зрения Blackslex, он будет видеть только цвет $$$c_i$$$ каждого соседа $$$u_i$$$ ($$$1 \leq i \leq d(v)$$$$$$^{\text{∗}}$$$) вершины $$$v$$$. Он должен выбрать некоторое $$$j$$$ ($$$1 \leq j \leq d(v)$$$) и перейти к вершине $$$u_j$$$, чтобы приблизиться к вершине $$$1$$$.
Обратите внимание, что соседи упорядочены произвольным образом. Он видит только цвета соседних вершин, а не вершину, на которой находится. Кроме того, он не знает индекс вершины, на которой находится, соседние вершины или любую другую вершину.
Ваша задача — реализовать стратегию как для агента, так и для Blackslex. Для агента вы должны окрасить каждую вершину в один из трех цветов. Для Blackslex вам даны $$$q$$$ запросов. В каждом запросе вас высаживают на произвольной и неизвестной вершине $$$v$$$ и дают цвет соседних вершин. Вы должны определить вершину, к которой следует перейти, чтобы приблизиться к вершине $$$1$$$.
$$$^{\text{∗}}$$$Количество соседей вершины $$$v$$$.
Ваш код будет запущен ровно два раза на каждом тесте. В первый раз вы будете Игроком A (Агентом), а во второй — Игроком B (Blackslex).
Входные данные первого запуска
Первая строка входных данных содержит строку first. Это нужно для того, чтобы ваша программа распознала, что это ее первый запуск, и она должна действовать как Игрок A.
Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \leq t \leq 10^4$$$). Описание наборов следует далее.
Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$n-1 \leq m \leq 10^5$$$) — количество вершин и ребер соответственно.
Следующие $$$m$$$ строк содержат информацию о ребрах. $$$i$$$-я ($$$1 \leq i \leq m$$$) строка содержит два целых числа $$$a_i$$$ и $$$b_i$$$. ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$) — вершина $$$a_i$$$ соединена с вершиной $$$b_i$$$ ребром $$$i$$$.
Гарантируется, что:
- Сумма $$$n$$$ и сумма $$$m$$$ не превышают $$$10^5$$$ по всем наборам входных данных.
- Граф в каждом наборе входных данных двудольный и связный. В нем нет дублирующихся ребер и петель.
Входные данные второго запуска
Первая строка входных данных содержит строку second. Это нужно для того, чтобы ваша программа распознала, что это ее второй запуск, и она должна действовать как Игрок B.
Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — то же значение $$$t$$$, что и в первом запуске. Описание наборов следует далее.
Первая строка каждого набора содержит одно целое число $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — количество запросов в этом наборе.
Первая строка каждого запроса содержит одно целое число $$$d(v)$$$ ($$$1 \leq d(v) \leq 10^5$$$) — количество соседей вершины $$$v$$$, на которой сейчас находится Blackslex.
Следующая строка каждого запроса содержит строку $$$c$$$ длиной $$$d(v)$$$ — $$$i$$$-й ($$$1 \leq i \leq d(v)$$$) символ строки — цвет соседней вершины $$$u_i$$$. Символы в строке — это r, g или b, представляющие красный, зеленый или синий.
Гарантируется, что:
- Сумма $$$q$$$ не превышает $$$10^5$$$ по всем запросам во всех наборах входных данных.
- Сумма $$$d(v)$$$ не превышает $$$2 \cdot 10^5$$$ по всем запросам во всех наборах входных данных.
- $$$v \neq 1$$$
Входные данные второго запуска не адаптивен. Другими словами, входные данные второго запуска не изменятся в разных запусках.
Взломы
Чтобы сделать взлом, используйте следующий формат:
Первая строка содержит два целых числа $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.
Описание наборов входных данных для первого запуска следует далее.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$n-1 \leq m \leq 10^5$$$) — количество вершин и ребер соответственно.
Следующие $$$m$$$ строк содержат информацию о ребрах. $$$i$$$-я ($$$1 \leq i \leq m$$$) строка содержит два целых числа $$$a_i$$$ и $$$b_i$$$. ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$) — вершина $$$a_i$$$ соединена с вершиной $$$b_i$$$ ребром $$$i$$$.
После этого следует описание наборов входных данных для второго запуска.
Первая строка каждого набора содержит одно целое число $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — количество запросов в этом наборе.
Первая строка каждого запроса содержит одно целое число $$$v$$$ ($$$2 \leq v \leq n$$$) — вершина, на которой высаживается Blackslex.
Вторая строка каждого запроса содержит $$$d(v)$$$ целых чисел $$$p_1, p_2, \ldots, p_{d(v)}$$$ ($$$1 \leq p_i \leq d(v)$$$, каждое число в $$$p$$$ различно) — порядок соседей, как следует; пусть $$$q_1 \lt q_2 \lt \ldots \lt q_{d(v)}$$$ будут соседями вершины $$$v$$$, тогда порядок ввода соседей — это $$$u_i = q_{p_i}$$$.
Должно выполняться следующее:
- Сумма $$$n$$$ и сумма $$$m$$$ не превышают $$$10^5$$$ по всем наборам входных данных в первом запуске.
- Граф в каждом наборе двудольный и связный. В нем нет дублирующихся ребер и самопетлей.
- Сумма $$$q$$$ не превышает $$$10^5$$$ по всем запросам во всех наборах входных данных .
- Сумма $$$d(v)$$$ не превышает $$$2 \cdot 10^5$$$ по всем наборам входных данных во втором запуске.
Для первого запуска, для каждого набора входных данных выведите одну строку $$$s$$$ длиной $$$n$$$ — $$$s_i$$$ ($$$1 \leq i \leq n$$$) — цвет $$$i$$$-й вершины, окрашенной агентом. Символы в строке — это r, g или b, представляющие красный, зеленый или синий.
Для второго запуска, для каждого запроса в каждом наборе входных данных выведите одно целое число $$$j$$$ ($$$1 \leq j \leq d(v)$$$) — $$$u_j$$$ — соседняя вершина, к которой Blackslex перейдет дальше.
first 2 7 8 1 2 1 6 3 2 4 2 6 4 4 7 5 6 5 7 4 4 1 2 1 3 4 2 4 3
rrgbggr rbbb
second 2 2 3 grr 3 gbr 1 2 rb
1 3 1
Граф и раскраска обоих примеров. Граф и раскраска вершин примера показаны на изображении выше.
Во втором запуске первый пример имеет два запроса.
Первый запрос на вершине $$$4$$$ с соседями, упорядоченными как вершина $$$6$$$, $$$2$$$ и $$$7$$$. Выбор первого соседа — это переход к вершине $$$6$$$.
Второй запрос на вершине $$$6$$$ с соседями, упорядоченными как вершина $$$5$$$, $$$4$$$ и $$$1$$$. Выбор третьего соседа — это переход к вершине $$$1$$$.
Во втором примере есть один запрос на вершине $$$2$$$ с соседями, упорядоченными как вершина $$$1$$$ и $$$4$$$. Выбор первого соседа — это переход к вершине $$$1$$$.
Обратите внимание, что пустые строки добавлены для удобства чтения. На самом деле наборы не имеют пустых строк.
