Submission #246771

#	Time	Username	Problem	Language	Result	Execution time	Memory
246771		LifeHappen__	Split the Attractions (IOI19_split)	C++14	100 / 100	167 ms	18936 KiB

split

#include <bits/stdc++.h>
#include "split.h"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

#define forinc(a, b, c) for(int a = b, _c = c; a <= _c; ++a)
#define fordec(a, b, c) for(int a = b, _c = c; a >= _c; --a)
#define rep(i, a) forinc(i, 1, a)
#define repv(i, a) forinc(i, 0, a - 1)
#define forv(a, b) for(auto &a : b)

#define ii pair<int, int>
#define fi first
#define se second
#define reset(f, x) memset(f, x, sizeof(f))
#define all(a) begin(a), end(a)
#define pb push_back
#define eb emplace_back
#define mp make_pair

#define bit(x, i) (x >> (i - 1) & 1ll)
#define on(x, i) (x | (1ll << (i - 1)))
#define off(x, i) (x & ~(1ll << (i - 1)))

const int N = 2e5 + 5;
vector <int> ad[N];
int id[N];

int root(int x) {return id[x] < 0 ? x : id[x] = root(id[x]);}
bool mer(int u, int v){
    if((u = root(u)) == (v = root(v))) return false;
    if(id[u] < id[v]) swap(u, v);
    id[u] += id[v];
    id[v] = u;
    return 1;
}
int to(int x) {return -id[root(x)];}
int sz[N], pd[N];
int ftr(int s) {
    function<void(int)> dfs = [&](int u) {
        sz[u] = 1;
        forv(v, ad[u]) if(v != pd[u]) {
            pd[v] = u;
            dfs(v);
            sz[u] += sz[v];
        }
    };
    dfs(0);
    int now=0;
    while(1) {
        ii mx = {-1, -1};
        forv(v, ad[now]) if(v != pd[now]) mx = max(mx, make_pair(sz[v], v));
        if(mx.first <= s) return now;
        now = mx.se;
    }
    assert(0);
}

vector <int> find_split(int n, int a, int b, int c, vector <int> p, vector <int> q) {
    int m = p.size();
    int ca = 1, cb = 2, cc = 3;
    vector <ii> pp;
    vector <int> dd(n, 0);
    pp.eb(a, ca); pp.eb(b, cb); pp.eb(c, cc);
    sort(all(pp)); tie(a, ca) = pp[0]; tie(b, cb) = pp[1], tie(c, cc) = pp[2];
    reset(id, -1);
    repv(i, m) {
        int u = p[i], v = q[i];
        if(mer(u, v)) ad[u].pb(v), ad[v].pb(u);
    }
    reset(id, -1);
    int rt = ftr(n - b);
    repv(i, n) {
        forv(v, ad[i]) {
            if(i != rt && v != rt) mer(i, v);
        }
    }
    repv(i, m) {
        int u = p[i], v = q[i];
        if(to(u) >= a || to(v) >= a) continue;
        if(u == rt || v == rt) continue;
        if(mer(u, v)) {
            ad[u].pb(v); ad[v].pb(u);
        }
    }
    function<void(int, int &, int, int)> dfs=[&](int u, int &cnt, int cl, int bl) {
        if(u == bl || !cnt || dd[u]) return 0;
        dd[u] = cl;
        cnt -= 1;
        forv(v, ad[u]) if(!dd[v]) {
            dfs(v, cnt, cl, bl);
        }
    };
    forv(v, ad[rt]) if(to(v) >= a) {
        dfs(v, a, ca, rt);
        dfs(rt, b, cb, -1);
        repv(i, n) if(!dd[i]) dd[i] = cc;
        break;
    }
    return dd;
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    if(fopen("inp.txt", "r")) freopen("inp.txt", "r", stdin);
    int n, m, a, b, c;
    cin >> n >> m >> a >> b >> c;
    vector <int> p(m), q(m);
    repv(i, m) cin >> p[i] >> q[i];
    vector <int> ans = find_split(n, a, b, c, p, q);
    forv(v, ans) cout << v << ' ';
}
*/

Compilation message (stderr)

split.cpp: In lambda function:
split.cpp:99:5: warning: control reaches end of non-void function [-Wreturn-type]
     };
     ^

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 24 / 24
• Subtask 5: 36 / 36