Submission #1288322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288322		al95ireyiz	Split the Attractions (IOI19_split)	C++20	0 / 100	59 ms	20508 KiB

split

#pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
#if !defined(ONLINE_JUDGE) and !defined(EVAL)
#include "template/debug.h"
#else
#define d(x...)
#endif
#define fr first
#define er erase
#define in insert
#define sc second
#define ll long long
#define pb push_back
#define vll vector<ll>
#define pll pair<ll,ll>
#define len(x) (ll) x.size()
#define all(x) x.begin(),x.end()
const ll INF = 1e9, INFL = 1e18;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll maxn = 1e5 + 5;

ll n, m, k = 0;

#include "split.h"

ll dsu[maxn], cap[maxn];
void build_dsu(ll _n){
    for(ll i = 0; i < _n; i ++) dsu[i] = i, cap[i] = 1;
}
ll find(ll x){
    if(dsu[x] == x) return x;
    return dsu[x] = find(dsu[x]);
}
ll merge(ll a, ll b){
    ll par_a = find(a), par_b = find(b);
    if(par_a == par_b) return 0;
    dsu[par_b] = par_a;
    cap[par_a] += cap[par_b];
    return 1;
}

vll g[maxn], tg[maxn];
vector<pll>ot, edg;
bitset<maxn>vis;
ll sz[maxn];
void get_size(ll u, ll p = -1){
    sz[u] = 1;
    for(auto v : tg[u]){
        if(v == p) continue;
        get_size(v, u);
        sz[v] += sz[u];
    }
}
void dfs(ll u, ll p = -1){
    for(auto v : tg[u]){
        if(v == p) continue;
        merge(u, v);
        dfs(v, u);
    }
}
ll get_cent(ll u, ll p = -1){
    for(auto v : tg[u]){
        if(v == p) continue;
        if(sz[v] > n / 2){
            get_cent(v, u);
        }
    }
    return u;
}
void fill1(ll u, vll &ve, ll le){
    vis[u] = 1;
    ve.pb(u);
    if(len(ve) == le) return;
    for(auto v : g[u]){
        if(vis[v]) continue;
        if(find(u) != find(v)) continue;
        fill1(v, ve, le);
        if(len(ve) == le) return;
    }
}
void fill2(ll u, vll &ve, ll le){
    vis[u] = 1;
    ve.pb(u);
    if(len(ve) == le) return;
    for(auto v : g[u]){
        if(vis[v]) continue;
        fill2(v, ve, le);
        if(len(ve) == le) return;
    }
}
pair<vll, vll>f(ll a, ll b){
    if(a > b) swap(a, b);
    // 7 balliq subtask : cycle (AC)

    // 11 balliq subtask : a = 1 (AC)

    // 22 balliq subtask : tree (AC)

    // demeli biz ele u - v cutu tapmaliyiq ki,
    // 1) u ve v arasinda edge olsun;
    // 2) bu edge-i silende v -nin subtree size-i >= a olsun ve u -nun subtree size-i >= b olsun;
    // ** Esas Observation(+60 pts): tree olmayan qraf ucun ise, spanning tree mentiqi ile tree-ye cevire bilerik.
    
    // n <= 2500
    // 0 <= u <= n - 1 ucun dfs at, gor hansindasa alinirmi
    vll ax, bx;
    build_dsu(n);
    // spanning tree duzelt
    for(ll i = 0; i < len(edg); i ++){
        auto [x, y] = edg[i];
        if(merge(x, y)) tg[x].pb(y), tg[y].pb(x);
        else ot.pb(edg[i]);
        g[x].pb(y), g[y].pb(x);
    }
    get_size(0);
    ll root = -1, cent = get_cent(0);
    vis[cent] = 1;
    build_dsu(n);
    for(auto v : tg[cent]) dfs(v, cent);

    for(auto v : tg[cent]){
        if(cap[find(v)] >= a){
            root = find(v);
            break;
        }
    }
    
    for(auto [x, y] : ot){
        if(root != -1) break;
        if(x == cent or y == cent) continue;
        merge(x, y);
        if(cap[find(x)] >= a){
            root = find(x);
            break;
        }
    }
    
    if(root == -1) return {{}, {}};
    fill1(root, ax, a);
    vis[cent] = 0;
    fill2(cent, bx, b);
    return {ax, bx};
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> _p, vector<int> _q) {
    n = _n;
    for(ll i = 0; i < n; i ++) g[i].clear(), tg[i].clear();
    ot.clear(); edg.clear();
    for(ll i = 0; i < len(_p); i ++){
        edg.pb({_p[i], _q[i]});
    }
    vector<int>cv(n);
    if(_a <= _c and _b <= _c){
        auto [ax, bx] = f(_a, _b);
        if(_a > _b) swap(ax, bx);
        if(len(ax) != _a) return cv;
        cv.assign(n, 3);
        for(auto i : ax) cv[i] = 1;
        for(auto i : bx) cv[i] = 2;
    }
    else if(_a <= _b and _c <= _b){
        auto [ax, cx] = f(_a, _c);
        if(_a > _c) swap(ax, cx);
        if(len(ax) != _a) return cv;
        cv.assign(n, 2);
        for(auto i : ax) cv[i] = 1;
        for(auto i : cx) cv[i] = 3;
    }
    else{
        auto [bx, cx] = f(_b, _c);
        if(_b > _c) swap(bx, cx);
        if(len(bx) != _b) return cv;
        cv.assign(n, 1);
        for(auto i : bx) cv[i] = 2;
        for(auto i : cx) cv[i] = 3;
    }
    return cv;
}
// void _() {
    
// }
// signed main() {
//     ll tm = clock();
//     cin.tie(0)->sync_with_stdio(0);
//     ll t = 1;
//     cin >> t;
//     for(ll tt = 1; tt <= t; tt ++) _();
//     cerr << "\n\033[1;31mTime: \033[1;30m" \
//         << (double)(clock()-tm)/1000000 << "\033[1;32m seconds\n";
// }

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