Submission #852394

#	Time	Username	Problem	Language	Result	Execution time	Memory
852394		serifefedartar	Naboj (COCI22_naboj)	C++17	110 / 110	298 ms	28852 KiB

naboj

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 2e5 + 5;

vector<vector<pair<int,int>>> graph;
int indeg[MAXN], outdeg[MAXN], vis[MAXN];
int main() {
	fast
	int n, m, a, b;
	cin >> n >> m;

	graph = vector<vector<pair<int,int>>>(n+1, vector<pair<int,int>>());
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		graph[a].push_back({b, 0});
		graph[b].push_back({a, 1});
		indeg[a]++;
		outdeg[b]++;
	}

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (indeg[i] == 0 || outdeg[i] == 0)
			q.push(i);
	}

	stack<pair<int,int>> ans;
	while (!q.empty()) {
		int node = q.front();
		q.pop();

		if (vis[node])
			continue;
		vis[node] = true;

		int state = -1;
		for (auto u : graph[node]) {
			if (vis[u.f])
				continue;

			if (u.s == 1)
				indeg[u.f]--;
			else
				outdeg[u.f]--;

			if (indeg[u.f] == 0 || outdeg[u.f] == 0)
				q.push(u.f);
			state = u.s;
		}

		if (state != -1)
			ans.push({node, !state}); 
	}

	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			cout << "-1\n";
			return 0;
		}
	}

	cout << ans.size() << "\n"; 
	while (!ans.empty()) {
		cout << ans.top().f << " " << ans.top().s << "\n";
		ans.pop();
	}
}

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