比赛 2024暑假C班集训E 评测结果 TTTTTAAAAA
题目名称 灾难 最终得分 50
用户昵称 彭欣越 运行时间 10.246 s
代码语言 C++ 内存使用 3.72 MiB
提交时间 2024-07-14 10:39:26
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=65555;
int n,head[N*2],res,tot,mk[N*2];
struct node {
    int idx,nxt;
}e[N*2];
void add (int x,int y) {
    e[++tot].idx=y;
    e[tot].nxt=head[x];
    head[x]=tot;
}
bool check (int idx) {
    //cout << idx <<' ';
    if (mk[idx]==1) {
        return 1;
    }
    if (mk[idx]==2) {
        return 0;
    }
    int flag=0,p=0;
    for (int i=head[idx];i;i=e[i].nxt) {
        p++;
        if (!check(e[i].idx)) flag=1;
    }
    if (p==0) {
        mk[idx]=2;
        return 0;
    }
    if (flag==0) {
        mk[idx]=1;
        return 1;
    }
    mk[idx]=2;
    return 0;
}
void dfs (int idx,int x) {
    if (idx==x) {
        dfs(idx+1,x);
        return;
    }
    if (idx>n) return;
    if (check(idx)) res++;
    //cout <<endl; 
    dfs(idx+1,x); 
}
int main () {
    freopen("catas.in","r",stdin);
    freopen("catas.out","w",stdout);
    cin >> n;
    for (int i=1;i<=n;i++) {
        while (1) {
            int a;
            cin >> a;
            if (a==0) break;
            add(i,a);
        }
    }
    for (int i=1;i<=n;i++) {
        res=0;
        mk[i]=1;
        dfs(1,i);
        for (int j=1;j<=n;j++) mk[j]=0;
        cout << res <<endl;
    }
    return 0;
}