Submission #1125401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125401		NotLinux	Naboj (COCI22_naboj)	C++20	110 / 110	359 ms	27700 KiB

naboj

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
void solve(){
	int n,m;
	cin >> n >> m;
	vector < int > ingraph[n] , outgraph[n];
	int indegree[n]={0} , outdegree[n]={0};
	for(int i = 0;i<m;i++){
		int a,b;
		cin >> a >> b;
		a-- , b--;
		ingraph[a].push_back(b);
		outgraph[b].push_back(a);
		indegree[a]++;
		outdegree[b]++;
	}
	queue < int > q;
	for(int i = 0;i<n;i++){
		if((indegree[i]==0) or (outdegree[i]==0)){
			q.push(i);
		}
	}
	int vis[n]={0};
	vector < pair < int , int > > ans;
	auto remove_edge = [&](int a , int b){
		indegree[a]--;
		outdegree[b]--;
	};
	while(sz(q)){
		int tmp = q.front();
		q.pop();
		if(vis[tmp])continue;
		vis[tmp] = 1;
		ans.push_back({tmp , indegree[tmp] > 0});
		for(auto itr : ingraph[tmp]){
			remove_edge(tmp , itr);
		}
		for(auto itr : outgraph[tmp]){
			remove_edge(itr , tmp);
		}
		for(auto itr : ingraph[tmp]){
			if(vis[itr] == 0 and ((indegree[itr]==0) or (outdegree[itr]==0))){
				q.push(itr);
			}
		}
		for(auto itr : outgraph[tmp]){
			if(vis[itr] == 0 and ((indegree[itr]==0) or (outdegree[itr]==0))){
				q.push(itr);
			}
		}
	}
	for(int i = 0;i<n;i++){
		if(vis[i] == 0){
			cout << -1 << endl;
			return;
		}
	}
	reverse(all(ans));
	cout << sz(ans) << endl;
	for(auto itr : ans)cout << itr.first+1 << " " << itr.second << '\n';
	cout << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase=1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

• Subtask 1: 15 / 15
• Subtask 2: 25 / 25
• Subtask 3: 70 / 70