#CSPJ2024D. 接龙(chain)

接龙(chain)

[CSP-J 2024] 接龙(chain)

题目描述

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

总共有 nn 个人参与这个接龙游戏,第 ii 个人会获得一个整数序列 SiS_i 作为他的词库。

一次游戏分为若干轮,每一轮规则如下:

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

为了强调合作,小 J 给了 nn 个参与游戏的人 qq 个任务,第 jj 个任务需要这 nn 个人进行一次游戏,在这次游戏里进行恰好 rjr_j 轮接龙,且最后一轮的接龙序列的最后一个元素恰好为 cjc_j。为了保证任务的可行性,小 J 请来你判断这 qq 个任务是否可以完成的,即是否存在一个可能的游戏过程满足任务条件。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 TT,表示数据组数。

接下来包含 TT 组数据,每组数据的格式如下:

第一行包含三个整数 n,k,qn, k, q,分别表示参与游戏的人数、接龙序列长度上限以及任务个数。

接下来 nn 行:

ii 行包含 (li+1)(l_i + 1) 个整数 li,Si,1,Si,2,,Si,lil_i, S_{i,1}, S_{i,2}, \dots , S_{i,l_i},其中第一个整数 lil_i 表示序列 SiS_i 的长度,接下来 lil_i 个整数描述序列 SiS_i

接下来 qq 行:

jj 行包含两个整数 rj,cjr_j, c_j,描述一个任务。

输出格式

对于每个任务:输出一行包含一个整数,若任务可以完成输出 1,否则输出 0。

样例 #1

样例输入 #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 解释】

在下文中,我们使用 {Ai}={A1,A2,,Ar}\{A_i\} = \{A_1, A_2, \dots , A_r\} 表示一轮游戏中所有的接龙序列,{pi}={p1,p2,,pr}\{p_i\} = \{p_1, p_2, \dots , p_r\} 表示对应的接龙的人的编号。由于所有字符均为一位数字,为了方便我们直接使用数字字符串表示序列。

  • 对于第一组询问,p1=1p_1 = 1A1=12A_1 = 12 是一个满足条件的游戏过程。
  • 对于第二组询问,可以证明任务不可完成。注意 p1=1p_1 = 1A1=1234A_1 = 1234 不是合法的游戏过程,因为此时 A1=4>k|A_1| = 4 > k
  • 对于第三组询问,{pi}={2,1}\{p_i\} = \{2, 1\}{Ai}={12,234}\{A_i\} = \{12, 234\} 是一个满足条件的游戏过程。
  • 对于第四组询问,可以证明任务不可完成。注意 {pi}={2,1,1}{Ai}={12,23,34}\{p_i\} = \{2, 1, 1\}、\{A_i\} = \{12, 23, 34\} 不是一个合法的游戏过程,因为尽管所有的接龙序列长度均不超过 kk,但第二轮和第三轮由同一个人接龙,不符合要求。
  • 对于第五组询问,{pi}={1,2,3,1,2,3}\{p_i\} = \{1, 2, 3, 1, 2, 3\}{Ai}={12,25,51,12,25,516}\{A_i\} = \{12, 25, 51, 12, 25, 516\} 是一个满足条件的游戏过程。
  • 对于第六组询问,可以证明任务不可完成。注意每个接龙序列的长度必须大于等于 22,因此 A1=1A_1 = 1 不是一个合法的游戏过程。
  • 对于第七组询问,所有人的词库均不存在字符 7\tt 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,其中前两组测试数据满足 n1000n \leq 1000r10r \leq 10、单组测试数据内所有词库的长度和 2000\leq 2000q1000q \leq 1000

【样例 5】

见选手目录下的 chain/chain5.in 与 chain/chain5.ans。

该样例满足特殊性质 B,其中前两组测试数据满足 n1000n \leq 1000r10r \leq 10、单组测试数据内所有词库的长度和 2000\leq 2000q1000q \leq 1000

【样例 6】

见选手目录下的 chain/chain6.in 与 chain/chain6.ans。

该样例满足特殊性质 C,其中前两组测试数据满足 n1000n \leq 1000r10r \leq 10、单组测试数据内所有词库的长度和 2000\leq 2000q1000q \leq 1000

【数据范围】

对于所有测试数据,保证:

  • 1T51 \leq T \leq 5
  • 1n1051 \leq n \leq 10^52k2×1052 \leq k \leq 2 \times 10^51q1051 \leq q \leq 10^5
  • 1li2×1051 \leq l_i \leq 2 \times 10^51Si,j2×1051 \leq S_{i,j} \leq 2 \times 10^5
  • 1rj1021 \leq r_j \leq 10^21cj2×1051 \leq c_j \leq 2 \times 10^5
  • l\sum l单组测试数据内所有 lil_i 的和,则 l2×105\sum l\leq 2\times 10^5
测试点 nn\leq rr\leq l\sum l\leq qq\leq 特殊性质
11 10310^3 11 20002000 10310^3
2,32,3 1010 55 2020 10210^2
4,54,5 10310^3 1010 20002000 10310^3 A
66 10510^5 10210^2 2×1052\times 10^5 10510^5
7,87,8 10310^3 1010 20002000 10310^3 B
9,109,10 10510^5 10210^2 2×1052\times 10^5 10510^5
11,1211,12 10310^3 1010 20002000 10310^3 C
13,1413,14 10510^5 10210^2 2×1052\times 10^5 10510^5
151715\sim 17 10310^3 1010 20002000 10310^3
182018\sim 20 10510^5 10210^2 2×1052\times 10^5 10510^5

特殊性质 A:保证 k=2×105k = 2 \times 10^5

特殊性质 B:保证 k5k ≤ 5

特殊性质 C:保证在单组测试数据中,任意一个字符在词库中出现次数之和均不超过 55