Submission #1152967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152967		borekking	Senior Postmen (BOI14_postmen)	C++20	55 / 100	618 ms	97888 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    int x, y;
    vector<set<int>> adj(n);
    for (int i = 0; i < m; i++) {
        cin >> x >> y; x--; y--;
        adj[x].insert(y);
        adj[y].insert(x);
    }
    // hierholzer
    vector<vector<int>> ans;
    set<int> nodes;
    for (int i = 0; i < n; i++){
        nodes.insert(i);
    }
    set<int> in;
    stack<int> sta;
    sta.push(0);
    while (nodes.size() || sta.size()) {
        if (sta.size() == 0) {
            sta.push(*nodes.begin());
            continue;
        }
        int node = sta.top();
        if (in.find(node) != in.end()) {
            int end = node;
            vector<int> vec;
            int nod = sta.top();
            sta.pop();
            do {
                vec.push_back(nod);
                in.erase(nod);
                nod = sta.top();
                sta.pop();
            } while (nod != end);
            ans.push_back(vec);
            sta.push(end);
            continue;
        }
        if (adj[node].size() == 0) {
            sta.pop();
            continue;
        }
        in.insert(node);
        int next = *adj[node].begin();
        adj[node].erase(next);
        adj[next].erase(node);
        if (adj[node].size() == 0) {
            nodes.erase(node);
        }
        if (adj[next].size() == 0) {
            nodes.erase(next);
        }
        sta.push(next);
    }
    for (vector<int> vec : ans) {
        for (int x : vec) {
            cout << x+1 << " ";
        }
        cout << "\n";
    }
    cout << flush;
    return 0;
}

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45