比赛 |
NOIP模拟赛by mzx Day2 |
评测结果 |
AAAAAAAAAA |
题目名称 |
森林大礼包 |
最终得分 |
100 |
用户昵称 |
宋逸群 |
运行时间 |
1.503 s |
代码语言 |
C++ |
内存使用 |
20.39 MiB |
提交时间 |
2016-10-20 20:21:00 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 100010
typedef long long ll;
const ll INF=1e9+7;
struct node{ll y,next;}e[MAXN*10];
ll n,len,Link[MAXN],v[MAXN],id[MAXN],q[MAXN*10];
inline ll read()
{
ll x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
void insert(ll x,ll y) {e[++len].next=Link[x];Link[x]=len;e[len].y=y;id[y]++;}
void topsort()
{
ll head=0,tail=0; v[0]=1;
for(ll i=0;i<=n;i++) if(!id[i]) q[++tail]=i;
while(++head<=tail)
{
ll x=q[head];
for(ll i=Link[x];i;i=e[i].next)
{
v[e[i].y]+=v[x]; v[e[i].y]%=INF;
if(--id[e[i].y]==0) q[++tail]=e[i].y;
}
}
}
int main()
{
freopen("three_squirrels.in","r",stdin);
freopen("three_squirrels.out","w",stdout);
n=read();
for(ll i=1;i<=n;i++)
{
ll T=read();
while(T--) {ll x=read(); insert(x,i);}
}
topsort();
printf("%lld\n",v[n]%INF);
return 0;
}