比赛 |
NOIP模拟赛by mzx Day2 |
评测结果 |
AAAAAAAAAA |
题目名称 |
森林大礼包 |
最终得分 |
100 |
用户昵称 |
FoolMike |
运行时间 |
1.591 s |
代码语言 |
C++ |
内存使用 |
24.31 MiB |
提交时间 |
2016-10-20 21:43:07 |
显示代码纯文本
- #include<cstdio>
- #include<algorithm>
- #include<queue>
- using namespace std;
- const int N=1000010,p=1e+9+7;
- inline int read(){
- int x=0;char ch=getchar();
- while (ch>'9'||ch<'0') ch=getchar();
- while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
- return x;
- }
- struct edge{
- int f,t;
- edge(int F=0,int T=0){f=F;t=T;}
- }w[N];
- int n,m,k[N],cnt[N],head[N],tail[N],next[N],sum;
- inline void add(int f,int t){
- sum++;w[sum]=edge(f,t);
- if (!head[f]) head[f]=tail[f]=sum;
- else tail[f]=next[tail[f]]=sum;
- }
- queue<int> Q;
- int main()
- {
- freopen("three_squirrels.in","r",stdin);
- freopen("three_squirrels.out","w",stdout);
- n=read();cnt[0]=1;
- for (int i=1;i<=n;i++){
- int x;k[i]=read();
- for (int j=1;j<=k[i];j++)
- x=read(),add(x,i);
- }
- for (int i=0;i<=n;i++)
- if (!k[i]) Q.push(i);
- while (!Q.empty()){
- int v=Q.front();Q.pop();
- for (int i=head[v];i;i=next[i]){
- int u=w[i].t;
- cnt[u]=(cnt[u]+cnt[v])%p;k[u]--;
- if (!k[u]) Q.push(u);
- }
- }
- printf("%d\n",cnt[n]);
- return 0;
- }