Submission #1153046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153046		borekking	Senior Postmen (BOI14_postmen)	C++20	100 / 100	491 ms	78488 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);
    }
    vector<vector<int>> ans;
    vector<bool> vis(n, 0);
    for (int i = 0; i < n; i++) {
        if (adj[i].size() == 0) {
            continue;
        }
        stack<pair<int, int>> sta;
        sta.push({i, -1});
        while (sta.size()) {
            int node, last;
            tie(node, last) = sta.top();
            if (vis[node]) {
                int end = node;
                vector<int> vec;
                int nod, las;
                tie(nod, las) = sta.top();
                do {
                    sta.pop();
                    vec.push_back(nod);
                    adj[nod].erase(las);
                    adj[las].erase(nod);
                    vis[nod] = 0;
                    tie(nod, las) = sta.top();
                } while (nod != end);
                ans.push_back(vec);

                continue;
            }
            if (adj[node].size() == 0) {
                break;
            }
            vis[node] = 1;
            int next = *adj[node].begin();
            if (next == last) {
                next = *(++adj[node].begin());
            }
            sta.push({next, node});
        }
    }
    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: 45 / 45