比赛 NOIP模拟赛by mzx Day2 评测结果 AAAAAAAAAA
题目名称 森林大礼包 最终得分 100
用户昵称 灰里城 运行时间 1.021 s
代码语言 C++ 内存使用 9.09 MiB
提交时间 2016-10-20 19:30:57
显示代码纯文本
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. #define mod 1000000007
  7. const int maxn=100010;
  8.  
  9. int tot=0,head[maxn],ru[maxn];
  10. struct E{
  11. int to,nxt;
  12. }e[maxn*10];
  13. int sum[maxn];
  14. queue<int> q;
  15.  
  16. int read(){
  17. char c; int x,f=1;
  18. while(c=getchar(),c<'0'||c>'9')
  19. if(c=='-')f=-1;
  20. x=(c^'0');
  21. while(c=getchar(),c>='0'&&c<='9')
  22. x=(x<<3)+(x<<1)+(c^'0');
  23. return x*f;
  24. }
  25. void Add(int s,int t){
  26. e[++tot].to=t; e[tot].nxt=head[s]; head[s]=tot;
  27. }
  28. int main(){
  29. freopen("three_squirrels.in","r",stdin);
  30. freopen("three_squirrels.out","w",stdout);
  31. int n=read();
  32. for(int i=1;i<=n;++i){
  33. int k=read();
  34. for(int j=1;j<=k;++j){
  35. int x=read();
  36. Add(x,i); ++ru[i];
  37. }
  38. }
  39. q.push(0); sum[0]=1;
  40. while(!q.empty()){
  41. int s=q.front(); q.pop();
  42. for(int i=head[s];i;i=e[i].nxt){
  43. int t=e[i].to;
  44. sum[t]=(sum[t]+sum[s])%mod; --ru[t];
  45. if(!ru[t])q.push(t);
  46. }
  47. }
  48. printf("%d\n",sum[n]);
  49. // getchar();getchar();
  50. fclose(stdin);fclose(stdout);
  51. return 0;
  52. }