比赛 |
NOIP模拟赛by mzx Day2 |
评测结果 |
AAAAAAAAAA |
题目名称 |
森林大礼包 |
最终得分 |
100 |
用户昵称 |
灰里城 |
运行时间 |
1.021 s |
代码语言 |
C++ |
内存使用 |
9.09 MiB |
提交时间 |
2016-10-20 19:30:57 |
显示代码纯文本
- #include <iostream>
- #include <cstdio>
- #include <queue>
- using namespace std;
-
- #define mod 1000000007
- const int maxn=100010;
-
- int tot=0,head[maxn],ru[maxn];
- struct E{
- int to,nxt;
- }e[maxn*10];
- int sum[maxn];
- queue<int> q;
-
- int read(){
- char c; int x,f=1;
- while(c=getchar(),c<'0'||c>'9')
- if(c=='-')f=-1;
- x=(c^'0');
- while(c=getchar(),c>='0'&&c<='9')
- x=(x<<3)+(x<<1)+(c^'0');
- return x*f;
- }
- void Add(int s,int t){
- e[++tot].to=t; e[tot].nxt=head[s]; head[s]=tot;
- }
- int main(){
- freopen("three_squirrels.in","r",stdin);
- freopen("three_squirrels.out","w",stdout);
- int n=read();
- for(int i=1;i<=n;++i){
- int k=read();
- for(int j=1;j<=k;++j){
- int x=read();
- Add(x,i); ++ru[i];
- }
- }
- q.push(0); sum[0]=1;
- while(!q.empty()){
- int s=q.front(); q.pop();
- for(int i=head[s];i;i=e[i].nxt){
- int t=e[i].to;
- sum[t]=(sum[t]+sum[s])%mod; --ru[t];
- if(!ru[t])q.push(t);
- }
- }
- printf("%d\n",sum[n]);
- // getchar();getchar();
- fclose(stdin);fclose(stdout);
- return 0;
- }