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