【MX-X6-T1】Subtask Dependency
题目描述
现在有一道 OI 题。这道题有 $n$ 个子任务,编号从 $1$ 到 $n$。编号为 $i$ 的子任务依赖 $d_i$ 个子任务,这些子任务的编号分别为 $a_{i,1},a_{i,2},\dots,a_{i,d_i}$。保证对于所有 $1\leq i\leq n,1\leq j\leq d_i$,有 $a_{i,j}<i$,即**一个子任务只会依赖编号小于自己的子任务**。注意一个子任务可能不依赖任何子任务。
一个选手的程序可以描述为一个长度为 $n$ 的 $0/1$ 序列 $p_1,p_2,\dots,p_n$,分别表示该程序能否通过第 $i$ 个子任务。
评测一个程序时,评测机会按照编号从小到大依次考虑每一个子任务。当考虑到第 $i$ 个子任务时:
- 如果该子任务依赖的子任务中存在一个子任务的状态为错误,则该子任务的状态为错误;
- 否则,评测机测试该子任务。如果选手的程序能通过该子任务,则该子任务状态为正确;否则状态为错误。
一个程序的得分是评测后状态为正确的子任务个数。
现在有 $m$ 个选手提交程序,你需要分别计算它们的得分。
输入输出格式
输入格式
第一行一个整数 $n$ 表示子任务个数。
接下来 $n$ 行,第 $i$ 行首先输入一个整数 $d_i$ 表示第 $i$ 个子任务依赖的子任务个数;接下来输入 $d_i$ 个整数 $a_{i,1},a_{i,2},\dots,a_{i,d_i}$ 表示依赖的子任务编号。保证所有 $a_{i,j}<i$。
接下来一行一个整数 $m$,表示选手程序个数。
接下来 $m$ 行,每行 $n$ 个整数,其中第 $i$ 行第 $j$ 个整数 $p_{i,j}$ 为 $0$ 表示第 $i$ 个选手的程序不能通过第 $j$ 个子任务;为 $1$ 表示第 $i$ 个选手的程序能通过第 $j$ 个子任务。
输出格式
输出 $m$ 行,第 $i$ 行输出第 $i$ 个选手的得分。
输入输出样例
输入样例 #1
3
0
1 1
1 2
3
1 1 1
1 0 1
0 0 0
输出样例 #1
3
1
0
输入样例 #2
10
0
1 1
1 2
3 1 2 3
4 1 4 2 3
0
5 6 4 5 2 1
0
1 4
1 9
10
1 0 0 1 1 0 1 0 0 0
1 0 1 0 1 0 1 0 1 0
1 0 1 1 1 1 1 1 0 1
1 1 0 1 1 0 1 1 0 1
1 1 0 1 0 0 0 1 1 1
1 1 0 1 0 1 0 1 1 1
1 0 0 1 0 1 1 1 0 1
1 1 0 1 1 1 0 0 1 1
1 1 1 0 0 0 0 0 1 1
1 0 0 0 1 1 1 0 1 1
输出样例 #2
1
1
3
3
3
4
3
3
3
2
说明
**【样例解释 #1】**
- 选手 1 的程序可以通过所有子任务,因此所有 $3$ 个子任务的结果均为正确;
- 选手 2 的程序不能通过子任务 2,因此子任务 2 会被判定为错误;由于子任务 3 依赖子任务 2,因此即使选手 2 的程序可以通过子任务 3,子任务 3 也会被判定为错误。该选手的程序的评测结果只有子任务 1 正确。
- 选手 3 的程序不能通过任何子任务,因此所有子任务结果均为错误。
**【数据范围】**
对于所有数据,满足 $1\leq n,m\leq 100$,$0\leq d_i<i$,$1\leq a_{i,j}<i$,$0\leq p_{i,j}\leq 1$,不存在 $i$ 和 $j_1\neq j_2$ 使得 $a_{i,j_1}=a_{i,j_2}$。
共 $10$ 组数据,具体限制如下:
- 对于第 $1,2$ 组数据,满足 $n=1$;
- 对于第 $3,4,5$ 组数据,满足对所有 $i$,有 $d_i\leq 1$;
- 对于其他数据,不满足任何附加限制。