比赛 |
2024国庆练习1 |
评测结果 |
AAAAAAAAAA |
题目名称 |
森林大礼包 |
最终得分 |
100 |
用户昵称 |
徐诗畅 |
运行时间 |
0.553 s |
代码语言 |
C++ |
内存使用 |
6.48 MiB |
提交时间 |
2024-10-04 17:42:15 |
显示代码纯文本
#include<bits/stdc++.h>
const int mod=1e9+7;
using namespace std;
const int N=100005;
int n,in[N],ans[N];
int cnt,head[N];
struct edge{
int v,next;
}e[N*10];
void addedge(int u,int v){
e[++cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int main(){
freopen("three_squirrels.in","r",stdin);
freopen("three_squirrels.out","w",stdout);
scanf("%d",&n);
for(int i = 0;i<=n;i++) head[i]=-1;
for(int i = 1;i<=n;i++){
scanf("%d",&in[i]);
for(int j= 1;j<=in[i];j++){
int v; scanf("%d",&v);
addedge(v,i);
}
}
queue<int> q;
for(int i = head[0];i!=-1;i=e[i].next){
int v=e[i].v; in[v]--; ans[v]++;
if(!in[v]) q.push(v);
}
while(!q.empty()){
int u = q.front(); q.pop();
for(int i = head[u];i!=-1;i=e[i].next){
int v=e[i].v;
in[v]--;
if(!in[v]) q.push(v);
ans[v]=(ans[v]+ans[u])%mod;
}
}
printf("%d",ans[n]);
return 0;
}