比赛 NOIP模拟赛by mzx Day2 评测结果 AAAAAAAAAA
题目名称 森林大礼包 最终得分 100
用户昵称 再见 运行时间 1.366 s
代码语言 C++ 内存使用 9.83 MiB
提交时间 2016-10-20 20:40:23
显示代码纯文本
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cctype>
  4.  
  5. const long long MOD=1e9+7;
  6.  
  7. inline int read(){
  8. int _x=0; char ch; bool flag=false;
  9. while(ch=getchar(),!isdigit(ch)) ch=='-'?flag=true:false;
  10. while(_x=_x*10+ch-'0',ch=getchar(),isdigit(ch));
  11. return flag?-_x:_x;
  12. }
  13.  
  14. int n,k,tot,Q[100010],qhead,tail,ru[100010],head[100010],next[1000010],to[1000010];
  15. long long ans[100010];
  16.  
  17. int main()
  18. {
  19. //freopen("a.txt","r",stdin);
  20. freopen("three_squirrels.in","r",stdin);
  21. freopen("three_squirrels.out","w",stdout);
  22. n=read();
  23. for(int i=1;i<=n;i++){
  24. k=read();
  25. for(int j=1;j<=k;j++){
  26. int x=read();
  27. ++tot;
  28. to[tot]=i;
  29. next[tot]=head[x];
  30. head[x]=tot;
  31. ru[i]++;
  32. }
  33. }
  34. ans[0]=1;
  35. for(int i=0;i<=n;i++)
  36. if(ru[i]==0)
  37. Q[tail++]=i;
  38. while(qhead<tail){
  39. int now=Q[qhead++];
  40. for(int p=head[now];p;p=next[p]){
  41. ans[to[p]]=(ans[to[p]]+ans[now])%MOD;
  42. ru[to[p]]--;
  43. if(!ru[to[p]]){
  44. Q[tail++]=to[p];
  45. }
  46. }
  47. }
  48. printf("%lld",ans[n]);
  49. return 0;
  50. }
  51.