Submission #1141006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141006		KindaGoodGames	Senior Postmen (BOI14_postmen)	C++17	0 / 100	0 ms	328 KiB

postmen

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

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

using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    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);
     
    while (S.size()) {
        int v = S.top();
        if (occ.count(v)) {  
            S.pop();
            do {
                cout << S.top() + 1 << " ";
                occ.erase(S.top());  S.pop();
            } while (S.top() != v);
            cout << "\n"; 
            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);
    } 
}

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