比赛 |
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;
}