比赛 |
2024国庆练习1 |
评测结果 |
AAAAAAAAAA |
题目名称 |
森林大礼包 |
最终得分 |
100 |
用户昵称 |
小金 |
运行时间 |
0.712 s |
代码语言 |
C++ |
内存使用 |
6.92 MiB |
提交时间 |
2024-10-04 16:35:01 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const long long mod=1e9+7;
const int N=100010,M=1000010;
int n,h[N],r[N],v[M],ne[M],tp[N],tot;
long long s[N];
void add(int x,int y)
{
tot++;
v[tot]=y;
ne[tot]=h[x];
h[x]=tot;
}
void tpp()
{
queue<int> q;
for(int i=0;i<=n;i++)
{
if(r[i]==0) q.push(i);
}
while(q.size())
{
int x=q.front();
q.pop();
tot++;
tp[tot]=x;
for(int i=h[x];i;i=ne[i])
{
int y=v[i];
r[y]--;
if(r[y]==0) q.push(y);
}
}
}
int main()
{
freopen("three_squirrels.in","r",stdin);
freopen("three_squirrels.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int k;
scanf("%d",&k);
for(int j=1;j<=k;j++)
{
int a;
scanf("%d",&a);
add(a,i);
r[i]++;
}
}
tot=-1;
tpp();
s[0]=1;
for(int i=0;i<=n;i++)
{
int x=tp[i];
for(int j=h[x];j;j=ne[j])
{
int y=v[j];
s[y]=(s[y]+s[x]%mod)%mod;
}
}
printf("%lld",s[n]);
return 0;
}