比赛 |
NOIP模拟赛by mzx Day2 |
评测结果 |
AAAAAAAAAA |
题目名称 |
森林大礼包 |
最终得分 |
100 |
用户昵称 |
Ostmbh |
运行时间 |
1.069 s |
代码语言 |
C++ |
内存使用 |
13.29 MiB |
提交时间 |
2016-10-20 21:54:53 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int maxn=100000+10;
long long f[maxn];
int vis[maxn]={0};
queue<int>q;
const int XTT=1000000000+7;
struct Edge{
int f,t,next;
Edge(){
next=0;
}
}E[maxn*10];
int head[maxn]={0};
int edge=1;
inline void addedge(int x,int y){
E[edge].f=x,E[edge].t=y,E[edge].next=head[x],head[x]=edge++;
}
inline void read(int &x){
x=0;
char c=getchar();
bool flag=0;
while(c<'0'||c>'9'){
if(c=='-')
flag=1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
if(flag)
x=-x;
}
int main(){
freopen("three_squirrels.in","r",stdin);
freopen("three_squirrels.out","w",stdout);
int n,x;
read(n);
for(int i=1;i<=n;i++){
read(vis[i]);
for(int j=1;j<=vis[i];j++){
read(x);
addedge(x,i);
}
}
f[0]=1;
q.push(0);
while(!q.empty()){
int cd=q.front();
q.pop();
for(int i=head[cd];i;i=E[i].next){
int u=E[i].t;
vis[u]--;
f[u]+=f[cd];
if(f[u]>=XTT)
f[u]-=XTT;
if(!vis[u])
q.push(u);
}
}
printf("%lld\n",f[n]);
return 0;
}