Олимпиадный тренинг

Задача . D. Игра со стеками

Задача

Темы: графы Деревья Перебор поиск в глубину и подобное реализация *3000

У вас есть \(n\) стеков \(r_1,r_2,\ldots,r_n\). Каждый стек содержит некоторое количество целых положительных чисел в диапазоне от \(1\) до \(n\).

Определим следующие функции:

function init(pos):
    stacks := массив, содержащий n стеков r[1], r[2], ..., r[n].
    return get(stacks, pos)

function get(stacks, pos):
    if stacks[pos] пуст:
        return pos
    else:
        new_pos := верхний элемент stacks[pos]
        удалить верхний элемент stacks[pos]
        return get(stacks, new_pos)

Вы хотите узнать значения, возвращаемые \(\texttt{init(1)}, \texttt{init(2)}, \ldots, \texttt{init(n)}\).

Заметим, что во время этих вызовов стеки \(r_1,r_2,\ldots,r_n\) не изменяются, поэтому вызовы \(\texttt{init(1)}, \texttt{init(2)}, \ldots, \texttt{init(n)}\) являются независимыми.

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

Первая строка ввода содержит одно целое число \(n\) (\(1\le n\le 10^5\)) — длина массива \(r\).

Каждая из последующих \(n\) строк содержит несколько целых чисел. Первое целое число \(k_i\) (\(0\le k_i\le 10^5\)) представляет собой количество элементов в \(i\)-м стеке, а следующие \(k_i\) положительных целых чисел \(c_{i,1},c_{i,2},\ldots,c_{i,k_i}\) (\(1\le c_{i,j}\le n\)) представляют элементы в \(i\)-м стеке. \(c_{i,1}\) - нижний элемент.

В каждом тесте \(\sum k_i\le 10^6\).

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

Необходимо вывести \(n\) значений, \(i\)-м из которых является значение, возвращаемое \(\texttt{init(i)}\).

Примечание

В первом примере:

При вызове \(\texttt{init(1)}\) присваивается \(\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}\), а затем вызывается \(\texttt{get(stacks, 1)}\).
- \(\texttt{stacks[1]}\) не пуст, присваивается \(\texttt{new_pos := 2}\) и удаляется верхний элемент \(\texttt{stacks[1]}\), в результате чего \(\texttt{stacks}\) станет \([[1,2],[3,1,2],[1,2,1]]\), а затем вызывается \(\texttt{get(stacks, 2)}\).
- \(\texttt{stacks[2]}\) не пуст, присваивается \(\texttt{new_pos := 2}\) и удаляется верхний элемент \(\texttt{stacks[2]}\), в результате чего \(\texttt{stacks}\) станет \([[1,2],[3,1],[1,2,1]]\), а затем вызывается \(\texttt{get(stacks, 2)}\).
- \(\texttt{stacks[2]}\) не пуст, присваивается \(\texttt{new_pos := 1}\) и удаляется верхний элемент \(\texttt{stacks[2]}\), в результате чего \(\texttt{stacks}\) станет \([[1,2],[3],[1,2,1]]\), а затем вызывается \(\texttt{get(stacks, 1)}\).
- \(\texttt{stacks[1]}\) не пуст, присваивается \(\texttt{new_pos := 2}\) и удаляется верхний элемент \(\texttt{stacks[1]}\), в результате чего \(\texttt{stacks}\) станет \([[1],[3],[1,2,1]]\), а затем вызывается \(\texttt{get(stacks, 2)}\).
- \(\texttt{stacks[2]}\) не пуст, присваивается \(\texttt{new_pos := 3}\) и удаляется верхний элемент \(\texttt{stacks[2]}\), в результате чего \(\texttt{stacks}\) станет \([[1],[],[1,2,1]]\), а затем вызывается \(\texttt{get(stacks, 3)}\).
- \(\texttt{stacks[3]}\) не пуст, присваивается \(\texttt{new_pos := 1}\) и удаляется верхний элемент \(\texttt{stacks[3]}\), в результате чего \(\texttt{stacks}\) станет \([[1],[],[1,2]]\), а затем вызывается \(\texttt{get(stacks, 1)}\).
- \(\texttt{stacks[1]}\) не пуст, присваивается \(\texttt{new_pos := 1}\) и удаляется верхний элемент \(\texttt{stacks[1]}\), в результате чего \(\texttt{stacks}\) станет \([[],[],[1,2]]\), а затем вызывается \(\texttt{get(stacks, 1)}\).
- \(\texttt{stacks[1]}\) пуст, возвращается \(1\).
При вызове \(\texttt{init(2)}\) присваивается \(\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}\), а затем вызывается \(\texttt{get(stacks, 2)}\).
- \(\texttt{stacks[2]}\) не пуст, присваивается \(\texttt{new_pos := 2}\) и удаляется верхний элемент \(\texttt{stacks[2]}\), в результате чего \(\texttt{stacks}\) станет \([[1,2,2],[3,1],[1,2,1]]\), а затем вызывается \(\texttt{get(stacks, 2)}\).
- \(\texttt{stacks[2]}\) не пуст, присваивается \(\texttt{new_pos := 1}\) и удаляется верхний элемент \(\texttt{stacks[2]}\), в результате чего \(\texttt{stacks}\) станет \([[1,2,2],[3],[1,2,1]]\), а затем вызывается \(\texttt{get(stacks, 1)}\).
- \(\texttt{stacks[1]}\) не пуст, присваивается \(\texttt{new_pos := 2}\) и удаляется верхний элемент \(\texttt{stacks[1]}\), в результате чего \(\texttt{stacks}\) станет \([[1,2],[3],[1,2,1]]\), а затем вызывается \(\texttt{get(stacks, 2)}\).
- \(\texttt{stacks[2]}\) не пуст, присваивается \(\texttt{new_pos := 3}\) и удаляется верхний элемент \(\texttt{stacks[2]}\), в результате чего \(\texttt{stacks}\) станет \([[1,2],[],[1,2,1]]\), а затем вызывается \(\texttt{get(stacks, 3)}\).
- \(\texttt{stacks[3]}\) не пуст, присваивается \(\texttt{new_pos := 1}\) и удаляется верхний элемент \(\texttt{stacks[3]}\), в результате чего \(\texttt{stacks}\) станет \([[1,2],[],[1,2]]\), а затем вызывается \(\texttt{get(stacks, 1)}\).
- \(\texttt{stacks[1]}\) не пуст, присваивается \(\texttt{new_pos := 2}\) и удаляется верхний элемент \(\texttt{stacks[1]}\), в результате чего \(\texttt{stacks}\) станет \([[1],[],[1,2]]\), а затем вызывается \(\texttt{get(stacks, 2)}\).
- \(\texttt{stacks[2]}\) пуст, возвращается \(2\).
При вызове \(\texttt{init(3)}\) присваивается \(\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}\), а затем вызывается \(\texttt{get(stacks, 3)}\).
- \(\texttt{stacks[3]}\) не пуст, присваивается \(\texttt{new_pos := 1}\) и удаляется верхний элемент \(\texttt{stacks[3]}\), в результате чего \(\texttt{stacks}\) станет \([[1,2,2],[3,1,2],[1,2]]\), а затем вызывается \(\texttt{get(stacks, 1)}\).
- \(\texttt{stacks[1]}\) не пуст, присваивается \(\texttt{new_pos := 2}\) и удаляется верхний элемент \(\texttt{stacks[1]}\), в результате чего \(\texttt{stacks}\) станет \([[1,2],[3,1,2],[1,2]]\), а затем вызывается \(\texttt{get(stacks, 2)}\).
- \(\texttt{stacks[2]}\) не пуст, присваивается \(\texttt{new_pos := 2}\) и удаляется верхний элемент \(\texttt{stacks[2]}\), в результате чего \(\texttt{stacks}\) станет \([[1,2],[3,1],[1,2]]\), а затем вызывается \(\texttt{get(stacks, 2)}\).
- \(\texttt{stacks[2]}\) не пуст, присваивается \(\texttt{new_pos := 1}\) и удаляется верхний элемент \(\texttt{stacks[2]}\), в результате чего \(\texttt{stacks}\) станет \([[1,2],[3],[1,2]]\), а затем вызывается \(\texttt{get(stacks, 1)}\).
- \(\texttt{stacks[1]}\) не пуст, присваивается \(\texttt{new_pos := 2}\) и удаляется верхний элемент \(\texttt{stacks[1]}\), в результате чего \(\texttt{stacks}\) станет \([[1],[3],[1,2]]\), а затем вызывается \(\texttt{get(stacks, 2)}\).
- \(\texttt{stacks[2]}\) не пуст, присваивается \(\texttt{new_pos := 3}\) и удаляется верхний элемент \(\texttt{stacks[2]}\), в результате чего \(\texttt{stacks}\) станет \([[1],[],[1,2]]\), а затем вызывается \(\texttt{get(stacks, 3)}\).
- \(\texttt{stacks[3]}\) не пуст, присваивается \(\texttt{new_pos := 2}\) и удаляется верхний элемент \(\texttt{stacks[3]}\), в результате чего \(\texttt{stacks}\) станет \([[1],[],[1]]\), а затем вызывается \(\texttt{get(stacks, 2)}\).
- \(\texttt{stacks[2]}\) пуст, возвращается \(2\).

Примеры

№	Входные данные	Выходные данные
1	3 3 1 2 2 3 3 1 2 3 1 2 1	1 2 2
2	5 5 1 2 4 3 4 6 1 2 5 3 3 4 6 1 1 4 4 4 2 9 3 1 4 2 3 5 5 1 2 4 4 4 1 3	1 1 1 1 1

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет