比赛 2024暑假C班集训E 评测结果 TTTATAAAAA
题目名称 灾难 最终得分 60
用户昵称 LikableP 运行时间 8.412 s
代码语言 C++ 内存使用 5.54 MiB
提交时间 2024-07-14 11:50:25
显示代码纯文本
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define fo(i, l, r) for(int i = (l); i <= (r); i++)
using namespace std;

vector <int> G[65535];
int gin[65535];
int vis[65535];
int disaster[65535];
int grass[65535];
int n;

int Topu(int st){
	queue <int> q;
	q.push(st);
	while(!q.empty()){
		int now = q.front();
		q.pop();
		for(auto x : G[now]) if(vis[x]) vis[x]--;
		for(auto x : G[now]) if(!vis[x] && !grass[x]) q.push(x);
	}
	int cnt = 0;
	fo(i, 1, n) if(!vis[i] && !grass[i]) cnt++;
	return cnt;
}

int main(){
	freopen("catas.in", "r", stdin);
	freopen("catas.out", "w", stdout);
	cin >> n;
	fo(i, 1, n){
		int from;
		while(cin >> from && from){
			G[from].push_back(i);
			gin[i]++;
		}
	}
	fo(i, 1, n) if(!gin[i]) grass[i] = true;
	fo(i, 1, n){
		copy(gin + 1, gin + n + 1, vis + 1);
		disaster[i] = Topu(i);
	}
	fo(i, 1, n) cout << disaster[i] << endl;
	return 0;
}