2024 CSP-J 第二轮 T4｜接龙

一、完整题目

题目描述

在玩惯了成语接龙之后，小 J 和他的朋友们发明了一个新的接龙规则。

总共有 n 个人参与这个接龙游戏，第 i 个人会获得一个整数序列 S_i 作为他的词库。

一次游戏分为若干轮，每一轮规则如下：

• n 个人中的某个人 p 带着他的词库 S_p 进行接龙。若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。
• 接龙的人选择一个长度在 [2,k] 的 S_p 的连续子序列 A 作为这一轮的接龙序列，其中 k 是给定的常数。若这是游戏的第一轮，那么 A 需要以元素 1 开头；否则，A 需要以上一轮接龙序列的最后一个元素开头。
• 序列 A 是序列 S 的连续子序列，当且仅当可以通过删除 S 的开头和结尾的若干元素（可以不删除）得到 A。

为了强调合作，小 J 给了 n 个参与游戏的人 q 个任务。第 j 个任务需要这 n 个人进行一次游戏，在这次游戏里进行恰好 r_j 轮接龙，且最后一轮接龙序列的最后一个元素恰好为 c_j。

请判断这 q 个任务是否可以完成，即是否存在一个可能的游戏过程满足任务条件。

输入格式

从文件 chain.in 中读入数据。

本题有多组测试数据。输入的第一行包含一个正整数 T，表示数据组数。

接下来包含 T 组数据，每组数据格式如下：

• 第一行包含三个整数 n,k,q，分别表示参与游戏的人数、接龙序列长度上限以及任务个数。
• 接下来 n 行：第 i 行包含 l_i+1 个整数 l_i,S_{i,1},S_{i,2},…,S_{i,l_i}。第一个整数 l_i 表示序列 S_i 的长度，接下来 l_i 个整数描述序列 S_i。
• 接下来 q 行：第 j 行包含两个整数 r_j,c_j，描述一个任务。

输出格式

输出到文件 chain.out 中。

对于每个任务，输出一行一个整数：若任务可以完成，输出 1；否则输出 0。

样例 1 输入

1
3 3 7
5 1 2 3 4 1
3 1 2 5
3 5 1 6
1 2
1 4
2 4
3 4
6 6
1 1
7 7

样例 1 输出

1
0
1
0
1
0
0

样例 1 解释

下面用 {A_i}={A_1,A_2,…,A_r} 表示各轮接龙序列，用 {p_i}={p_1,p_2,…,p_r} 表示各轮参与者编号。样例中的元素都是一位数，因此把序列连写展示。

• 第一组询问：p_1=1，A_1=12 是一个合法过程。
• 第二组询问无法完成。p_1=1，A_1=1234 不合法，因为 |A_1|=4>k。
• 第三组询问：{p_i}={2,1}，{A_i}={12,234} 是一个合法过程。
• 第四组询问无法完成。{p_i}={2,1,1}，{A_i}={12,23,34} 虽然每段长度均不超过 k，但第二轮和第三轮由同一个人接龙。
• 第五组询问：{p_i}={1,2,3,1,2,3}，{A_i}={12,25,51,12,25,516} 是一个合法过程。
• 第六组询问无法完成。每个接龙序列的长度必须至少为 2，所以 A_1=1 不合法。
• 第七组询问中，所有人的词库都没有数字 7，因此无法完成。

其余附加样例

• 样例 2 见选手目录下的 chain/chain2.in 与 chain/chain2.ans，满足测试点 1 的限制。
• 样例 3 见选手目录下的 chain/chain3.in 与 chain/chain3.ans，满足测试点 2 的限制。
• 样例 4 见选手目录下的 chain/chain4.in 与 chain/chain4.ans，满足特殊性质 A；其中前两组数据还满足 n≤1000、r≤10、Σl≤2000、q≤1000。
• 样例 5 见选手目录下的 chain/chain5.in 与 chain/chain5.ans，满足特殊性质 B；其中前两组数据还满足 n≤1000、r≤10、Σl≤2000、q≤1000。
• 样例 6 见选手目录下的 chain/chain6.in 与 chain/chain6.ans，满足特殊性质 C；其中前两组数据还满足 n≤1000、r≤10、Σl≤2000、q≤1000。

数据范围与测试点

对于所有测试数据，保证：

• 1≤T≤5；
• 1≤n≤10^5，2≤k≤2×10^5，1≤q≤10^5；
• 1≤l_i≤2×10^5，1≤S_{i,j}≤2×10^5；
• 1≤r_j≤100，1≤c_j≤2×10^5；
• 设 Σl 为单组数据内所有 l_i 之和，则 Σl≤2×10^5。

• 特殊性质 A：保证 k=2×10^5。
• 特殊性质 B：保证 k≤5。
• 特殊性质 C：单组数据中，任意一个数在所有词库里的出现次数之和不超过 5。