Submission #246404

#	Time	Username	Problem	Language	Result	Execution time	Memory
246404		LifeHappen__	Split the Attractions (IOI19_split)	C++14	0 / 100	117 ms	19064 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;

#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 = 1e5 + 5;
int n, m;
int a, b, c, dd[N], req;
vector <int> ad[N];
ii ed[N];
struct dsu {
    vector <int> id;
    dsu(int n) {
        id.resize(n, -1);
    }
    void init(int n) {
        id.resize(n, -1);
    }
    int root(int x) {return id[x] < 0 ? x : id[x] = root(id[x]);}
    bool com(int u, int v) {
        u = root(u), v = root(v);
        if(u == v) return false;
        if(id[u] < id[v]) swap(u, v);
        id[u] += id[v];
        id[v] = u;
        return true;
    }
    bool same(int u, int v) {
        return root(u) == root(v);
    }
    int sz(int x) {
        return -id[root(x)];
    }
};

int sz[N], pd[N], cnt = 0;

int find_cen(int siz) {
    function<void(int, int)> dfs = [&](int u, int par) {
        sz[u] = 1;
        forv(v, ad[u]) if(v != par) {
            pd[v] = u;
            dfs(v, u);
            sz[u] += sz[v];
        }
    };
    dfs(0, -1);
    int u = 0;
    pair<int, int> mx = {-1, -1};
    while(1) {
        mx = {-1, -1};
        forv(v, ad[u]) if(v != pd[u]) mx = max(mx, make_pair(sz[v], v));
        if(mx.fi <= siz) return u;
        u = mx.se;
    }
    assert(0);
}

void col(int u, int par, int &cnt, int cl) {
    if(!cnt) return;
    if(dd[u]) return;
    if(u == par) return;
    dd[u] = cl;
    cnt--;
    forv(v, ad[u]) col(v, par, cnt, cl);
}

vector <int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
    n = _n, a = _a, b = _b, c = _c;
    int ca, cb, cc;
    vector <ii> _;
    _.eb(a, 1); _.eb(b, 2); _.eb(c, 3);
    sort(all(_));
    tie(a, ca) = _[0];
    tie(b, cb) = _[1];
    tie(c, cc) = _[2];
    m = p.size();
    repv(i, m) {
        int u = p[i], v = q[i];
        //ad[u].pb(v); ad[v].pb(u);
        ed[i + 1] = {u, v};
    }
    dsu f(n);
    rep(i, m) {
        int u = ed[i].fi, v = ed[i].se;
        if(f.com(u, v)) {
            ad[u].pb(v); ad[v].pb(u);
        }
    }
    int r = find_cen(n - b);
    f.init(n);
    forinc(i, 0, n - 1) {
        forv(v, ad[i]) {
            if(i != r && v != r) f.com(i, v);
        }
    }
    forinc(i, 0, m - 1) {
        int u = p[i], v = q[i];
        if(f.sz(u) >= a || f.sz(v) >= a) continue;
        if(u != r && v != r) {
            if(f.com(u, v)) {
                ad[u].pb(v); ad[v].pb(u);
            }
        }
    }
    forv(v, ad[r]) if(f.sz(v) >= a) {
        col(v, r, a, ca);
        col(r, -1, b, cb);
        forinc(i, 0, n - 1) if(!dd[i]) dd[i] = cc;
        break;
    }
    vector <int> result;
    forinc(i, 0, n - 1) result.pb(dd[i]);
    return result;
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    #define task "split"
    if(fopen("inp.txt", "r")) {
        freopen("inp.txt", "r", stdin);
    }
    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 << ' ';
}
*/

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