Submission #1141278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141278		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);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
        
    vector<bool> used(m);
    vector<vector<pii>> adj(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].push_back({ b,i });
        adj[b].push_back({ a,i });
    } 
    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)) {   
            cout << S.top() + 1 << " ";
            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();
        // as long as we have an invalid edge
        while (adj[v].size() && used[adj[v][0].second]) {
            swap(adj[v][0], adj[v][adj[v].size() - 1]);
            adj[v].pop_back();
        }
        if (!adj[v].size()) break;
        // use an edge
        used[adj[v][0].second] = true;
        int u = adj[v][0].first;

        // erasur 
        swap(adj[v][0], adj[v][adj[v].size() - 1]);
        adj[v].pop_back();


        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