think-cell Round 1 |
---|
Закончено |
Это интерактивная задача.
У Алисы есть дерево $$$T$$$, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Алиса покажет дерево $$$T$$$ Бобу. После того как Боб увидит $$$T$$$, он должен назвать Алисе две перестановки $$$p_1$$$ и $$$p_2$$$ чисел $$$[1, 2, \ldots, n]$$$.
Затем Алиса сыграет $$$q$$$ раундов следующей игры:
Обратите внимание, что все раунды независимы друг от друга. В частности, значения $$$a$$$, $$$u$$$ и $$$v$$$ могут быть разными в разных раундах.
Боб озадачен, поскольку он знает только решение с HLD, которое требует $$$O(\log(n))$$$ запросов в каждом раунде. Поэтому ему нужна ваша помощь, чтобы выиграть игру.
$$$^\dagger$$$ $$$\operatorname{MEX}$$$ набора чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$c$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует взаимодействие по каждому набору входных данных.
Первая строка каждого набора входных данных содержит два положительных целых числа $$$n$$$ и $$$q$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^4$$$) — количество вершин в $$$T$$$ и количество раундов соответственно.
Следующие $$$n-1$$$ строк содержат по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), обозначающие ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что заданные ребра образуют дерево.
Гарантируется, что суммы $$$n$$$ и $$$q$$$ по всем наборам входных данных не превосходит $$$10^5$$$ и $$$10^4$$$ соответственно.
Также гарантируется, что сумма значений $$$n \cdot q$$$ не превосходит $$$3 \cdot 10^6$$$.
После завершения чтения ребер дерева необходимо вывести две перестановки $$$p_1$$$ и $$$p_2$$$ чисел $$$[1, 2, \ldots, n]$$$.
Для этого в отдельной строке выведите $$$n$$$ целых чисел — перестановку $$$p_1$$$.
В следующей строке выведите $$$n$$$ целых чисел — перестановку $$$p_2$$$.
Алиса начнет играть в игру.
Для каждого раунда необходимо считать два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$). Вам нужно найти $$$\operatorname{MEX}$$$ значений вершин на пути из $$$u$$$ в $$$v$$$.
Чтобы сделать запрос, выведите «? $$$t$$$ $$$l$$$ $$$r$$$» без кавычек, где $$$t$$$ равно $$$1$$$ или $$$2$$$ и $$$1 \leq l \leq r \leq n$$$. После этого вы должны прочитать одно целое число — ответ на ваш запрос $$$\min_{i=l}^{r} a_{p_{t,i}}$$$. В каждом раунде можно сделать не более $$$5$$$ таких запросов для каждого раунда.
Когда вы хотите вывести ответ, выведите «! $$$x$$$» ($$$1 \leq x, y \leq n$$$) без кавычек. После этого считайте одно целое число, которое в нормальной ситуации будет равно $$$1$$$.
Если вместо корректного ответа вы получаете целое число $$$-1$$$, это означает, что ваша программа сделала некорректный запрос, превысила лимит запросов или дала неправильный ответ на предыдущем наборе входных данных. Чтобы получить вердикт Неправильный ответ, ваша программа должна немедленно завершиться. В противном случае вы можете получить произвольный вердикт, поскольку ваше решение будет продолжать читать из закрытого потока.
После вывода запроса или ответа не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
Взломы
Чтобы сделать взлом, используйте следующий формат.
Первая строка должна содержать целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных должна содержать два целых числа $$$n$$$ и $$$q$$$ ($$$2 \leq n \leq 10^5$$$; $$$1 \leq q \leq 10^4$$$) — количество вершин в $$$T$$$ и количество раундов, соответственно.
Следующие $$$n-1$$$ строк должны содержать по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), означающие ребро между вершинами $$$u$$$ и $$$v$$$. Данные ребра должны образовывать дерево.
Для каждого из $$$q$$$ раундов сначала выведите в отдельной строке перестановку чисел $$$[0, 1, 2, \ldots, n-1]$$$ — массив $$$a$$$, который выберет Алиса в начале раунда.
В следующей строке выведите два различных целых числе $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq v$$$, $$$u \neq v$$$) — вершины, являющиеся концам пути, про который спросит Алиса.
Сумма значений $$$n$$$ и сумма значений $$$q$$$ по всем наборам входных данных не должны превышать $$$10^5$$$ и $$$10^4$$$ соответственно.
Сумма значений $$$n \cdot q$$$ не должна превышать $$$3 \cdot 10^6$$$.
1 3 1 1 2 2 3 2 3 1 0 1
1 2 3 2 1 3 ? 1 2 3 ? 2 1 3 ! 0
В первом примере взаимодействие происходит следующим образом.
Решение | жюри | объяснение |
1 | Имеется 1 набор входных данных. | |
3 1 | Дерево $$$T$$$ состоит из $$$3$$$ вершин, и Алиса будет играть только один раунд. | |
1 2 | Первое ребро $$$T$$$ | |
2 3 | Второе ребро $$$T$$$ | |
1 2 3 | Перестановка $$$p_1$$$ | |
2 1 3 | Перестановка $$$p_2$$$ | |
Алиса переставляет элементы $$$a$$$ и получает $$$a=[0,2,1]$$$, прежде чем выдать вершины для единственного раунда. | ||
2 3 | Вершины для раунда | |
? 1 2 3 | 1 | $$$\min(a_{p_{1,2}},a_{p_{1,3}})=\min(a_2,a_3)=1$$$ |
? 2 1 3 | 0 | $$$\min(a_{p_{2,1}},a_{p_{2,2}},a_{p_{2,3}})=\min(a_2,a_1,a_3)=0$$$ |
! 0 | 1 | Учитывая ответы на запросы, очевидно, что $$$\operatorname{MEX}$$$ равен $$$0$$$. Поскольку вывод верен, жюри отвечает $$$1$$$. |
После каждого набора входных данных обязательно считывайте $$$1$$$ или $$$-1$$$.
Название |
---|