Submission #1094895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094895		andrewp	Senior Postmen (BOI14_postmen)	C++14	0 / 100	0 ms	348 KiB

postmen

//Dedicated to my love, ivaziva
#pragma GCC optimize("Ofast") 
#include <bits/stdc++.h> 
using namespace std;  
 
using pii = pair<int, int>;
using ll = int64_t; 
 
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n';   

const int maxn = 5e5;    

int32_t main()  {
    ios::sync_with_stdio(false); cin.tie(nullptr);  
    cout.tie(nullptr); cerr.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> u(m), v(m);
    vector<bool> removed(m), was(n);
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i], --u[i], --v[i];
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    vector<int> p(n);
    stack<int> stk;
    function<void(int)> dfs = [&](int x) {
        if (was[x]) {
            while (!stk.empty()) {
                int node = stk.top();
                stk.pop();
                cout << node + 1 << ' ';
                was[node] = true;
                if (node == x) {
                    break;
                }
            }
            cout << '\n';
        }
        stk.push(x);
        was[x] = true;
        for (; p[x] < (int)(g[x].size()); p[x]++) {
            int c = g[x][p[x]];
            if (removed[c]) {
                continue;
            }
            removed[c] = true;
            int nxt = (x ^ u[c] ^ v[c]);
            p[x]++; 
            dfs(nxt);
            return;
        }
        stk.pop();
        was[x] = false; 
    };
    for (int i = 0; i < n; i++) {
        dfs(i);
    }
    return 0;
}

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