比赛 |
2024国庆练习1 |
评测结果 |
AAAAAAAAAA |
题目名称 |
森林大礼包 |
最终得分 |
100 |
用户昵称 |
健康铀 |
运行时间 |
0.578 s |
代码语言 |
C++ |
内存使用 |
11.73 MiB |
提交时间 |
2024-10-04 16:37:35 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
#define MOD 1000000007
#define LL long long
LL n, idx = 1, head[N], sr[N], res[N];
struct Edge {
LL u, v, next;
}ed[N<<1];
queue<LL> q;
inline LL get() {
LL num = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') num = num * 10 + c - '0', c = getchar();
return num;
}
inline void add(LL u, LL v) {
ed[idx].v = v;
ed[idx].next = head[u];
head[u] = idx++;
}
int main() {
freopen("three_squirrels.in", "r", stdin);
freopen("three_squirrels.out", "w", stdout);
n=get();
fill(head, head+n+1, -1);
for (LL i=1;i<=n;i++) {
sr[i]=get();
for(LL j=0;j<sr[i];j++)
add(get(),i);
}
for (LL i=head[0];i;i=ed[i].next) {
LL v=ed[i].v;
sr[v]--;
res[v]++;
if(!sr[v])
q.push(v);
}
while(!q.empty()) {
LL cur=q.front();
q.pop();
for (LL i=head[cur];i;i=ed[i].next) {
LL v=ed[i].v;
sr[v]--;
res[v]=(res[v]+res[cur])%MOD;
if(!sr[v])
q.push(v);
}
}
printf("%lld",res[n]);
return 0;
}