Submission #726764

#	Time	Username	Problem	Language	Result	Execution time	Memory
726764		Tigerpants	Senior Postmen (BOI14_postmen)	C++17	0 / 100	1095 ms	804 KiB

postmen

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
#include <set>
#include <map>
#include <numeric>
#include <random>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef set<ll> sll;
typedef vector<sll> vsll;
typedef vector<bool> vb;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define mp(a, b) make_pair(a, b)
#define sz(a) a.size()
#define pb(a) push_back(a)

ll N, M;
vsll g;

vvll cycles;

mt19937 r;
uniform_int_distribution<ll> dist(0, 1000000000);

vb vis;
vb onS;

bool DFS(ll cur, ll par) {
    if (onS[cur]) {
        // found new cycle
        onS[cur] = false;
        vis[cur] = false;
        cycles.pb(vll());
        cycles.back().pb(cur);
        g[cur].erase(par);
        g[par].erase(cur);
        M--;
        return true;
    }
    if (vis[cur]) return false;
    onS[cur] = true; vis[cur] = true;
    vll neigh(g[cur].begin(), g[cur].end());
    shuffle(neigh.begin(), neigh.end(), r);
    for (vll::iterator nxt = neigh.begin(); nxt != neigh.end(); nxt++) {
        if (*nxt == par) continue;
        if (DFS(*nxt, cur)) {
            if (onS[cur]) {
                onS[cur] = false;
                vis[cur] = false;
                cycles.back().pb(cur);
                g[cur].erase(par);
                g[par].erase(cur);
                M--;
                return true;
            } //else {
                // end of cycle
                onS[cur] = true;
            //}
        }
    }
    onS[cur] = false;
    return false;
}

void find_cycle() {
    ll nxt = dist(r) % N;
    if (sz(g[nxt])) {
        fill_n(vis.begin(), N, false);
        fill_n(onS.begin(), N, false);
        DFS(nxt, -1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    r.seed(123456);

    cin >> N >> M;
    g.resize(N);
    rep(i, 0, M) {
        ll tmpa, tmpb;
        cin >> tmpa >> tmpb;
        tmpa--; tmpb--;
        g[tmpa].insert(tmpb);
        g[tmpb].insert(tmpa);
    }

    vis.resize(N, false);
    onS.resize(N, false);

    while (M != 0) {
        find_cycle();
    }

    for (vvll::iterator cycle = cycles.begin(); cycle != cycles.end(); cycle++) {
        for (vll::iterator itr = cycle->begin(); itr != cycle->end(); itr++) {
            cout << (*itr) + 1 << " ";
        }
        cout << "\n";
    }
    cout << flush;

    return 0;
}

// if we have a node of odd degree -> not possible
// else we can just generate random cycles repeatedly...
// hmm, this has worstcase N^2

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