UOJ Logo Universal Online Judge

UOJ

#870. 【统一省选2024】最长待机

附件下载 统计

精灵程序员小 ω 和 小 拥有无限的寿命,因此在写代码之余,它们经常玩一些对抗游戏来打发时间。尽管如此,时间还是太多,于是它们发明了一款专用于消磨时间的游戏:最长待机。

为了了解最长待机的规则,首先要了解精灵们使用的编程语言 Sleep++ 的规则:

  • 程序由 n 个函数组成,第 i(1in) 个函数具有种类 ei 和子函数编号序列 Qi=(Qi,1,Qi,2,,Qi,li)Qi 可以为空,此时 li0

  • n 以及所有的 eiQi 可以由程序员任意给出,但它们需要满足以下所有条件:

    • n1
    • 1inei{0,1}
    • 1inQi 中元素两两不同且均为 [i+1,n] 中的整数;
    • 2jn恰好有一个 Qi(1in) 包含了 j
  • 调用函数 i(1in) 时,按顺序执行如下操作:

    • ei=0,令变量 ri1;否则程序员需要立即为 ri 输入一个正整数值
    • Qi 为空,程序等待 ri 秒;否则重复以下操作 ri 次:
      • 按顺序调用编号为 Qi,1,Qi,2,,Qi,li 的函数。
  • 若一个种类为 1 的函数 j 被调用多次,则其每次调用都需要输入 rj

  • 我们认为,在函数调用中,除了“等待 r 秒”之外的操作不消耗任何时间,即函数调用、运行和输入都在瞬间完成。因此,一个时刻内程序员可能输入多个数。

可以证明,调用任意一个 Sleep++ 程序的任意一个函数,无论如何设定输入,消耗的时间总是有限的。

“最长待机”的游戏规则如下:

  • ω 和 小 准备好各自的 Sleep++ 程序并选择各自程序中的一个函数。它们互相知晓对方程序的结构以及选择的函数。

  • 在时刻 0,小 ω 和 小 同时调用自己选择的函数,游戏开始。

  • 在时刻 tt0),双方可以看到对方在时刻 0(t1) 输入的所有数字,并相应调整自己在时刻 t 输入的数字,但双方无法得知对方在时刻 t 输入的数字。

  • 函数调用先结束的一方输掉游戏,另一方胜利。两个调用同时结束算作平局。

ω 和 小 都是绝顶聪明的,在它们眼中,如果有一方存在必胜策略,那么这局游戏是不公平的。换言之,双方都不存在必胜策略的游戏是公平的。

ω 写了一个 n 个函数的 Sleep++ 程序并进行了 m 次操作,操作有以下两种:

  • 操作一:给出 k,将 ek 修改为 (1ek)
  • 操作二:给出 k,与小 玩一局“最长待机”,开始时小 ω 会调用自己的函数 k

信奉极简主义,它希望对于每一局游戏设计出函数个数最少的程序,使得选择其中某个函数能让这局游戏是公平的。你能帮它求出最少所需的函数个数吗?

可以证明,小 总是能设计一个程序并选择其中一个函数,使得游戏是公平的。

输入格式

输入的第一行包含两个正整数 n,m,表示小 ω 的程序中函数的个数以及操作次数。

接下来 n 行,第 i 行若干个整数,描述小 ω 程序中的函数 i

  • 前两个整数 ei,li 表示函数种类和子函数编号序列长度;
  • 接下来 li 个整数 Qi,1,Qi,2,,Qi,li 描述子函数编号序列。

接下来 m 行,第 j 行两个整数 oj,kj 描述一次操作,其中 oj=1 表示操作一,oj=2 表示操作二。

输出格式

对于每个操作二输出一行一个整数,表示小 的程序中最少所需的函数个数。

样例 #1

样例输入 #1

3 6
0 2 2 3
0 0
0 0
2 1
1 3
2 1
1 3
1 2
2 1

样例输出 #1

3
3
1

提示

【样例 1 解释】

  • 对于前两次游戏,小 可以给出与小 ω 完全一致的程序并在游戏开始时调用函数 1。可以证明不存在函数个数更少的方案。

  • 对于第三次游戏,小 可以给出一个仅包含一个种类为 1 的函数的程序,并在游戏开始时调用函数 1

    • 在时刻 0,小 ω 输入其程序中的 r2,小 输入其程序中的 r1
      • 注意:r 变量在小 ω 和小 的程序之间是独立的,不会互相影响。
    • 输入完成后,小 ω 的程序在时刻 (r2+1) 结束,小 的程序在时刻 r1 结束。
    • 由于两人在时刻 0 互不知道对方的决策,不能保证 (r2+1)r1 的大小关系,故双方均不存在必胜策略,这局游戏是公平的。

【样例 2】

见附件中的 sleep2.in/ans

该组数据满足特殊性质 AD。

【样例 3】

见附件中的 sleep3.in/ans

该组数据满足特殊性质 BD。

【样例 4】

见附件中的 sleep4.in/ans

该组数据满足特殊性质 D。

【样例 5】

见附件中的 sleep5.in/ans

该组数据满足特殊性质 C。

【子任务】

对于所有测试数据,

  • 1n5×1051m2×105
  • 1inei{0,1},$0 \le l_i
  • 1in,1jlii<Qi,jn
  • 1in,1p<qliQi,pQi,q
  • 2jn,恰好有一个 Qi(1in) 包含了 j
  • 1jm1oj21kjn
测试点编号 n m 特殊性质
12 3 24
3 80 400 AD
4 80 400 BD
56 80 400 D
7 3×105 105 AD
8 3×105 105 BD
910 3×105 105 D
11 3×105 105 A
12 3×105 105 BC
13 3×105 105 B
1415 3×105 105 C
1617 3×105 105
1819 5×105 2×105 A
20 5×105 2×105 BC
21 5×105 2×105 B
2223 5×105 2×105 C
2425 5×105 2×105

特殊性质 A:保证

  • 任意时刻 e1 均为 0
  • 2inli1
  • 操作二的 k 均为 1

特殊性质 B:保证

  • 操作二的 k 满足当时的 ek1

特殊性质 C:保证

  • 2iniQi2
  • 1in,序列 Qi 单调递增。

特殊性质 D:保证

  • 操作二不超过 10 个;
  • 操作二的 k 均为 1

时间限制:2s 3.5s

空间限制:1024MB