比赛 NOIP模拟赛by mzx Day2 评测结果 AAAAAAAAAA
题目名称 森林大礼包 最终得分 100
用户昵称 FoolMike 运行时间 1.591 s
代码语言 C++ 内存使用 24.31 MiB
提交时间 2016-10-20 21:43:07
显示代码纯文本
  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<queue>
  4. using namespace std;
  5. const int N=1000010,p=1e+9+7;
  6. inline int read(){
  7. int x=0;char ch=getchar();
  8. while (ch>'9'||ch<'0') ch=getchar();
  9. while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
  10. return x;
  11. }
  12. struct edge{
  13. int f,t;
  14. edge(int F=0,int T=0){f=F;t=T;}
  15. }w[N];
  16. int n,m,k[N],cnt[N],head[N],tail[N],next[N],sum;
  17. inline void add(int f,int t){
  18. sum++;w[sum]=edge(f,t);
  19. if (!head[f]) head[f]=tail[f]=sum;
  20. else tail[f]=next[tail[f]]=sum;
  21. }
  22. queue<int> Q;
  23. int main()
  24. {
  25. freopen("three_squirrels.in","r",stdin);
  26. freopen("three_squirrels.out","w",stdout);
  27. n=read();cnt[0]=1;
  28. for (int i=1;i<=n;i++){
  29. int x;k[i]=read();
  30. for (int j=1;j<=k[i];j++)
  31. x=read(),add(x,i);
  32. }
  33. for (int i=0;i<=n;i++)
  34. if (!k[i]) Q.push(i);
  35. while (!Q.empty()){
  36. int v=Q.front();Q.pop();
  37. for (int i=head[v];i;i=next[i]){
  38. int u=w[i].t;
  39. cnt[u]=(cnt[u]+cnt[v])%p;k[u]--;
  40. if (!k[u]) Q.push(u);
  41. }
  42. }
  43. printf("%d\n",cnt[n]);
  44. return 0;
  45. }