比赛 |
NOIP模拟赛by mzx Day2 |
评测结果 |
AAAAWWWWWW |
题目名称 |
森林大礼包 |
最终得分 |
40 |
用户昵称 |
Sky_miner |
运行时间 |
1.364 s |
代码语言 |
C++ |
内存使用 |
33.88 MiB |
提交时间 |
2016-10-20 18:47:16 |
显示代码纯文本
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(ll &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline ll cat_max(const ll &a,const ll &b){return a>b ? a:b;}
inline ll cat_min(const ll &a,const ll &b){return a<b ? a:b;}
const ll maxn = 100010;
const ll maxm = 1000010;
struct Edge{
ll to,next;
}G[maxm<<1];
ll head[maxn],cnt,ind[maxn],num[maxn];
void add(ll u,ll v){
G[++cnt].to = v;
G[cnt].next = head[u];
++ind[v];
head[u] = cnt;
}
ll q[maxn],l,r=-1;
int main(){
freopen("three_squirrels.in","r",stdin);
freopen("three_squirrels.out","w",stdout);
ll n;read(n);
for(ll i=1,x,k;i<=n;++i){
read(k);
while(k--) read(x),add(x,i);
}
for(ll i=0;i<=n;++i) if(!ind[i]) q[++r] = i;
num[0] = 1;
while(l <= r){
ll u = q[l++];
for(ll i = head[u];i;i=G[i].next){
num[G[i].to] += num[u];
if(!(--ind[G[i].to])) q[++r] = G[i].to;
}
}
printf("%lld",num[n]);
//getchar();getchar();
fclose(stdin);fclose(stdout);
return 0;
}