Submission #1140997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140997		KindaGoodGames	Senior Postmen (BOI14_postmen)	C++20	0 / 100	0 ms	324 KiB

postmen

#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

using namespace std;


int main() {
    int n, m;
    cin >> n >> m;

    vector<set<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].insert(b);
        adj[b].insert(a);
    }

    vector<int> trav;
    set<int> occ;
    set<int> left;
    for (int i = 0; i < n; i++) {
        left.insert(i);
    }
    stack<int> S;
    S.push(0);

    vector<vector<int>> paths;
    while (S.size()) {
        int v = S.top();
        if (occ.count(v)) {
            vector<int> p;
            p.push_back(S.top()); S.pop();
            do {
                occ.erase(S.top());
                p.push_back(S.top()); S.pop();
            } while (S.top() != v);
            occ.erase(S.top());
            p.push_back(S.top()); 
            paths.push_back(p);
            if (adj[S.top()].size() == 0) {
                S.pop(); 
            }
            if (S.empty() && left.size()) {
                S.push(*left.begin());
            }
            if (S.empty()) break;
        }

         v = S.top();
         int u = *adj[v].begin();
         adj[u].erase(v);
         adj[v].erase(u);
         if (adj[v].size() == 0) left.erase(v);
         if (adj[u].size() == 0) left.erase(u);
         S.push(u);
         occ.insert(v); 
    }

    for (auto p : paths) {
        for (auto v : p) {
            cout << v << " ";
        }
        cout << endl;
    }
}

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