比赛 |
NOIP模拟赛by mzx Day2 |
评测结果 |
AAAAAAAAAA |
题目名称 |
森林大礼包 |
最终得分 |
100 |
用户昵称 |
再见 |
运行时间 |
1.366 s |
代码语言 |
C++ |
内存使用 |
9.83 MiB |
提交时间 |
2016-10-20 20:40:23 |
显示代码纯文本
#include<cstdio>
#include<cstdlib>
#include<cctype>
const long long MOD=1e9+7;
inline int read(){
int _x=0; char ch; bool flag=false;
while(ch=getchar(),!isdigit(ch)) ch=='-'?flag=true:false;
while(_x=_x*10+ch-'0',ch=getchar(),isdigit(ch));
return flag?-_x:_x;
}
int n,k,tot,Q[100010],qhead,tail,ru[100010],head[100010],next[1000010],to[1000010];
long long ans[100010];
int main()
{
//freopen("a.txt","r",stdin);
freopen("three_squirrels.in","r",stdin);
freopen("three_squirrels.out","w",stdout);
n=read();
for(int i=1;i<=n;i++){
k=read();
for(int j=1;j<=k;j++){
int x=read();
++tot;
to[tot]=i;
next[tot]=head[x];
head[x]=tot;
ru[i]++;
}
}
ans[0]=1;
for(int i=0;i<=n;i++)
if(ru[i]==0)
Q[tail++]=i;
while(qhead<tail){
int now=Q[qhead++];
for(int p=head[now];p;p=next[p]){
ans[to[p]]=(ans[to[p]]+ans[now])%MOD;
ru[to[p]]--;
if(!ru[to[p]]){
Q[tail++]=to[p];
}
}
}
printf("%lld",ans[n]);
return 0;
}