比赛 |
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]);
}