Submission #575877

#	Time	Username	Problem	Language	Result	Execution time	Memory
575877		eecs	Naboj (COCI22_naboj)	C++17	110 / 110	799 ms	61048 KiB

naboj

#include <bits/stdc++.h>
using namespace std;

const int maxn = 200010;
int n, m, c0[maxn], c1[maxn];
bool vis[maxn];
set<pair<int, int>> G[maxn];
vector<array<int, 2>> res;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        G[u].emplace(v, 1), G[v].emplace(u, 0);
        c0[u]++, c1[v]++;
    }
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (!c0[i] || !c1[i]) Q.push(i);
    }
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();
        if (vis[x]) continue;
        res.push_back({x, c0[x] ? 1 : 0}), vis[x] = 1;
        for (auto &e : G[x]) if (!vis[e.first]) {
            (e.second ? c1[e.first] : c0[e.first])--;
            G[e.first].erase({x, !e.second});
            if (!c0[e.first] || !c1[e.first]) Q.push(e.first);
        }
    }
    if (count(vis + 1, vis + n + 1, 0)) cout << "-1\n", exit(0);
    cout << res.size() << "\n";
    reverse(res.begin(), res.end());
    for (auto &p : res) {
        cout << p[0] << " " << p[1] << "\n";
    }
    return 0;
}

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