oj.uz

Submission #852386

# Submission time Handle Problem Language Result Execution time Memory
852386 2023-09-21T17:47:17 Z serifefedartar Naboj (COCI22_naboj) C++17
0 / 110
 99 ms 18004 KB 
#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();
		vis[node] = true;
		q.pop();

		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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 18004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -