Codeforces Round 960 (Div. 2) |
---|
Закончено |
Это сложная версия задачи. Единственное отличие — это ограничение на количество запросов.
Это интерактивная задача.
Вам дано дерево из $$$n$$$ вершин с вершиной $$$1$$$ в качестве корневой.
В одной из вершин спрятан крот. Чтобы найти его положение, вы можете выбрать вершину $$$x$$$ ($$$1 \le x \le n$$$) и сделать запрос к жюри. После этого жюри вернет $$$1$$$, если крот находится в поддереве вершины $$$x$$$. В противном случае жюри вернет $$$0$$$. Если жюри возвращает $$$0$$$ и крот не находится в корневой вершине $$$1$$$, крот переместится в вершину-родителя той вершины, в которой он находится в данный момент.
Используя не более $$$160$$$ операций, найдите текущую вершину, в которой находится крот.
Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Описание наборов входных данных следует ниже.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 5000$$$).
Следующая $$$n-1$$$ строка описывает ребра дерева. Каждая строка содержит два целых числа, разделенные пробелом, $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$), обозначающие ребро между вершинами $$$u_i$$$ и $$$v_i$$$.
Гарантируется, что входные данные представляют собой дерево.
Интерактор в этой задаче не является адаптивным. Другими словами, вершина, где изначально находится крот, зафиксирована в каждом наборе входных данных и не меняется во время взаимодействия.
Чтобы сделать запрос, вам нужно выбрать вершину $$$x$$$ ($$$1 \le x \le n$$$) и вывести строку следующего вида:
После этого вы получите:
Вы можете сделать не более $$$160$$$ запросов такого вида для каждого набора входных данных.
Затем, если вы определили текущую вершину, где находится крот, выведите строку следующего вида:
Обратите внимание, что эта строка не считается запросом и не учитывается при подсчете количества заданных запросов.
После этого переходите к следующему набору входных данных.
Если вы сделаете более $$$160$$$ запросов во время взаимодействия, ваша программа должна немедленно завершиться, и вы получите вердикт Неправильный ответ. В противном случае вы можете получить произвольный вердикт, потому что ваше решение будет продолжать читать из закрытого потока.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
Взломы
Чтобы сделать взлом, используйте следующий формат:
Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 100$$$). Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ ($$$2 \le n \le 5000$$$, $$$1 \le x \le n$$$), описывающие размер дерева и начальное положение крота.
Следующая $$$n-1$$$ строка описывает ребра дерева. Каждая строка содержит два целых числа, разделенные пробелом, $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$), обозначающие ребро между вершинами $$$u_i$$$ и $$$v_i$$$.
Входные данные обязаны представлять собой дерево.
2 2 1 2 1 6 1 2 1 3 1 4 4 5 5 6 0 0 1
? 2 ! 2 ? 2 ? 6 ? 4 ! 4
В первом наборе входных данных крот изначально находится в вершине $$$2$$$.
Для запроса «? 2», жюри возвращает $$$1$$$, потому что крот находится в поддереве вершины $$$2$$$. После этого запроса крот не перемещается.
Ответ $$$2$$$ — это текущая вершина, где находится крот, поэтому ответ считается правильным.
Во втором наборе входных данных крот изначально находится в вершине $$$6$$$.
Для запроса «? 2», жюри возвращает $$$0$$$, потому что крот не находится в поддереве вершины $$$2$$$. После этого запроса крот перемещается из вершины $$$6$$$ в вершину $$$5$$$.
Для запроса «? 6», жюри возвращает $$$0$$$, потому что крот не находится в поддереве вершины $$$6$$$. После этого запроса крот перемещается из вершины $$$5$$$ в вершину $$$4$$$.
Для запроса «? 4», жюри возвращает $$$1$$$, потому что крот находится в поддереве вершины $$$4$$$. После этого запроса крот не перемещается.
Ответ $$$4$$$ — это текущая вершина, где находится крот, поэтому ответ считается правильным.
Обратите внимание, что приведенный пример предназначен только для понимания условия, и запросы в примере не гарантируют определение уникального положения крота.
Название |
---|