比赛 NOIP模拟赛by mzx Day2 评测结果 AAAAAAAAAA
题目名称 森林大礼包 最终得分 100
用户昵称 Cydiater 运行时间 1.107 s
代码语言 C++ 内存使用 18.56 MiB
提交时间 2016-10-20 19:19:47
显示代码纯文本
//A
//by Cydiater
//2016.10.20
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <ctime>
#include <cmath>
using namespace std;
#define ll long long
#define up(i,j,n)		for(int i=j;i<=n;i++)
#define down(i,j,n)		for(int i=j;i>=n;i--)
#define FILE "three_squirrels"
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
const int mod=1e9+7;
inline int read(){
	char ch=getchar();int x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int N,indu[MAXN],K,head,tail,v[MAXN],q[MAXN],len=0,LINK[MAXN];
struct edge{
	int y,next;
}e[MAXN];
namespace solution{
	inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}
	void init(){
		N=read();
		memset(LINK,0,sizeof(LINK));
		memset(indu,0,sizeof(indu));
		memset(v,0,sizeof(v));v[0]=1;
		up(i,1,N){
			K=read();
			up(j,1,K){
				int y=read();
				insert(y,i);indu[i]++;
			}
		}
	}
	void slove(){
		head=1;tail=0;
		up(i,0,N)if(indu[i]==0)q[++tail]=i;
		for(;head<=tail;head++){
			int node=q[head];
			for(int i=LINK[node];i;i=e[i].next){
				(v[e[i].y]+=v[node])%=mod;
				if((--indu[e[i].y])==0)q[++tail]=e[i].y;
			}
		}
	}
	void output(){
		cout<<v[N]<<endl;
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	init();
	slove();
	output();
	return 0;
}