【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$; - 对于其他数据,不满足任何附加限制。