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