比赛 NOIP模拟赛by mzx Day2 评测结果 RRRRRRRRRR
题目名称 森林大礼包 最终得分 0
用户昵称 YouSiki 运行时间 0.020 s
代码语言 C++ 内存使用 2.34 MiB
提交时间 2016-10-20 19:38:00
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const signed N = 100005;
int n, hd[N], nt[N], to[N], tot, cnt[N], k[N], que[N];
signed main(void) {
	scanf("%d", &n);
	memset(hd, -1, sizeof(hd)), tot = 0;
	for (int i = 1; i <= n; ++i) {
		int ki; scanf("%d", &ki); k[i] = ki;
		for (int j = 1; j <= ki; ++j) {
			int aij; scanf("%d", &aij);
			nt[tot] = hd[aij]; to[tot] = i; hd[aij] = tot++;
		}
	}
	int head = 0, tail = 0; que[tail++] = 0; cnt[0] = 1;
	while (head != tail) {
		int top = que[head++];
		for (int i = hd[top]; ~i; i = nt[i]) {
			cnt[to[i]] += cnt[top];
			if (--k[to[i]] == 0)que[tail++] = to[i];
		}
	}
	printf("%d\n", cnt[n]);
}