oj.uz

Submission #726764

# Submission time Handle Problem Language Result Execution time Memory
726764 2023-04-19T10:31:15 Z Tigerpants Senior Postmen (BOI14_postmen) C++17
0 / 100
 500 ms 804 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Execution timed out 1088 ms 468 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Execution timed out 1090 ms 340 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 3 ms 804 KB Output is correct
5 Execution timed out 1095 ms 456 KB Time limit exceeded
6 Halted 0 ms 0 KB -