제출 #1152928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152928		borekking	Senior Postmen (BOI14_postmen)	C++20	38 / 100	1094 ms	20648 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

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
    set<int> nodes;
    for (int i = 0; i < n; i++) {
        nodes.insert(i);
    }
    vector<vector<int>> ans;
    while (nodes.size()) {
        int start = *nodes.begin();
        stack<pii> sta;
        sta.push({start, -1});
        vector<bool> vis(n, 0);
        while (sta.size()) {
            int node, par;
            tie(node, par) = sta.top();
            if (vis[node]) {
                break;
            }
            vis[node] = 1;
            int next = *adj[node].begin();
            if (next == par) {
                next = *(++((adj[node].begin())));
            }
            sta.push({next, node});
        } 
        vector<int> vec;
        int end = sta.top().first;
        int nod, las;
        tie(nod, las) = sta.top();
        sta.pop();
        do {
            adj[nod].erase(las);
            adj[las].erase(nod);
            if (adj[nod].size() == 0) {
                nodes.erase(nod);
            }
            if (adj[las].size() == 0) {
                nodes.erase(las);
            }

            tie(nod, las) = sta.top();
            sta.pop();
            vec.push_back(nod);
        } while (nod != end);
        ans.push_back(vec);
    }
    for (vector<int> vec : ans) {
        for (int x : vec) {
            cout << x+1 << " ";
        }
        cout << "\n";
    }
    cout << flush;
    return 0;
}

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