4164. [CF1889D] Game of Stack

【题目背景】

因为大样例可能有点问题，这里下发一下编译好的std文件

std.zip

运行方式：

打开cmd，定位到目标文件夹，直接输入：std.exe 输入文件 输出文件

虽然是原，但是我们不妨整个月计小剧场（

【题目描述】

W 公司拥有空间折跃相关奇点，因此，W 公司员工在战斗中经常使用折跃速攻的战术。

在一次作战任务中，作为W公司三级员工的你制定了一个折跃作战计划。

计划将空间分成了 n 个节点，为了提高打击效率，他给每个节点预定了折跃通道，每个节点 i 有 ki 条折跃通道，记为 f(i, [1 ~ ki])，在第 j 次到达节点 i 后会经过通道到达节点 f(i, ki - j + 1)，在作战中，员工将位于某一节点并开始折跃，不断经过折跃通道到达下一个节点，直到第 kx + 1 次到达点 x，此时 x 点没有通道，员工就结束了作战。

为了制定下一步计划，你需要快速得到每个节点开始折跃最终会在哪个节点结束。

形式化题意：

一个 n 个节点的图，每个节点 i 有一个大小为 ki 的栈。

我们重置每一个栈，然后从一个节点 x 开始，经过一个点时就取出栈顶元素 y 然后到达 y 节点直到到达一个点的栈为空

求出每个节点 i 开始最终到达的节点。

【输入格式】

第一行一个整数 n。

之后 n 行，先为一个整数 ki，接着 ki 个数表示 fi。

注意：第一个数是栈底，最后一个数是栈顶

【输出格式】

一行 i 个整数分别表示从 i 开始最后的位置。

【样例输入 1】

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

【样例输出 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

【样例输出 2】

1 1 1 1 1

【样例说明】

【数据规模与约定】

对于前 40% 的数据：n <= 1e3，k 之和  <= 1e4

对于 100% 的数据：n <= 1e5，k 之和  <= 1e6 

下发样例

【来源】

CodeForces

见题号