Submission #1230911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230911		siewjh	Povjerenstvo (COI22_povjerenstvo)	C++20	100 / 100	274 ms	59324 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
vector<int> adj[MAXN], radj[MAXN], ans;
int od[MAXN];
bool dd[MAXN];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int nodes, edges; cin >> nodes >> edges;
	for (int i = 0; i < edges; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b); radj[b].push_back(a);
		od[a]++;
	}
	queue<int> q; int id = 1;
	for (int i = 1; i <= nodes; i++)
		if (od[i] == 0)
			q.push(i);
	while (id <= nodes){
		while (!q.empty()){
			int x = q.front(); q.pop();
			ans.push_back(x); dd[x] = 1;
			for (int px : radj[x]){
				if (dd[px]) continue;
				dd[px] = 1;
				for (int ppx : radj[px]){
					if (dd[ppx]) continue;
					od[ppx]--;
					if (od[ppx] == 0) q.push(ppx);
				}
			}
		}
		while (id <= nodes && dd[id]) id++;
		if (id <= nodes){
			ans.push_back(id); dd[id] = 1;
			vector<int> vx;
			for (int px : adj[id])
				if (!dd[px]){
					dd[px] = 1; vx.push_back(px);
				}
			for (int px : radj[id])
				if (!dd[px]){
					dd[px] = 1; vx.push_back(px);
				}
			for (int px : vx){
				if (dd[px]) continue;
				dd[px] = 1;
				for (int ppx : radj[px]){
					if (dd[ppx]) continue;
					od[ppx]--;
					if (od[ppx] == 0) q.push(ppx);
				}
			}
		}
	}
	cout << ans.size() << '\n';
	for (int x : ans) cout << x << ' ';
}

• Subtask 1: 13 / 13
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33