Submission #749780

#	Time	Username	Problem	Language	Result	Execution time	Memory
749780		grogu	Split the Attractions (IOI19_split)	C++14	40 / 100	120 ms	31692 KiB

split

#include "split.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())

using namespace std;
const ll maxn = 200005;
ll n,m;
vector<ll> g[maxn];
vector<ll> c[maxn];
vector<ll> e[maxn];
ll dsu[maxn],sz[maxn],tsz = 0;
ll x,y,xid,yid;
ll poc,col,colid;
bool ok;
ll sub[maxn];
ll par[maxn];
bool vis[maxn];
vector<ll> ans;
void dfs(ll u,ll p){
    sub[u] = 1;
    par[u] = p;
    vis[u] = 1;
    for(ll s : g[u]){
        if(vis[s]) continue;
        dfs(s,u);
        e[u].pb(s);
        e[s].pb(u);
        sub[u]+=sub[s];
    }
    if(sub[u]>=x&&n-sub[u]>=y){
        poc = u; col = x; colid = xid; ok = 1;
    }
    if(sub[u]>=y&&n-sub[u]>=x){
        poc = u; col = y; colid = yid; ok = 1;
    }
}
void dfscol(ll u,ll p,ll col,ll &z){
    if(z){
        ans[u] = col;
        z--;
    }
    for(ll s : e[u]){
        if(s==p) continue;
        dfscol(s,u,col,z);
    }
}
ll cen(ll u,ll p){
    for(ll s : e[u]){
        if(s==p) continue;
        if(sub[s]*2>n) return cen(s,u);
    }
    return u;
}
void dfscomp(ll u,ll p){
    dsu[u] = tsz;
    sz[tsz]++;
    for(ll s : e[u]){
        if(s==p) continue;
        dfscomp(s,u);
    }
}
ll curcnt = 0;
ll use[maxn];
void dfscheck(ll u,ll st){
    curcnt+=sz[u];
    vis[u] = 1;
    if(curcnt>=x){
        use[u] = st;
        ok = 1;
        return;
    }
    for(ll s : c[u]){
        if(vis[s]) continue;
        dfscheck(s,st);
        if(ok) return;
    }
}
void dfscol2(ll u,ll col,ll &z){
    if(z) ans[u] = col,z--;
    else return;
    for(ll s : g[u]) if(use[s]&&!ans[s]) dfscol2(s,col,z);
}
void dfscol3(ll u,ll col,ll &z){
    if(z) ans[u] = col,z--;
    else return;
    for(ll s : g[u]) if(!ans[s]) dfscol3(s,col,z);
}
vector<int> find_split(int N, int A,int B,int C, vector<int> p, vector<int> q) {
    n = N;
    m = si(p);
    vector<pll> v;
    v.pb({A,1});
    v.pb({B,2});
    v.pb({C,3});
    sort(all(v));
    x = v[0].fi; xid = v[0].sc;
    y = v[1].fi; yid = v[1].sc;
    for(ll i = 1;i<=m;i++){
        ll x = p[i-1] + 1;
        ll y = q[i-1] + 1;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(1,1);
    ans.resize(n+1);
    if(ok){
        ll tmp = col;
        dfscol(poc,par[poc],colid,col);
        tmp^=y;
        tmp^=x;
        dfscol(par[poc],poc,colid^xid^yid,tmp);
        for(ll i = 1;i<=n;i++){
            if(ans[i]==0) ans[i] = v[2].sc;
        }
        reverse(all(ans));
        ans.popb();
        reverse(all(ans));
        return ans;
    }
    ll root = cen(1,1);
    for(ll j : e[root]){
        ++tsz;
        dfscomp(j,root);
    }
    for(ll i = 1;i<=n;i++){
        if(i==root) continue;
        for(ll j : g[i]){
            if(j==root) continue;
            c[dsu[i]].pb(dsu[j]);
            c[dsu[j]].pb(dsu[i]);
        }
    }
    fill(vis,vis+1+n,0);
    for(ll i = 1;i<=tsz;i++){
        if(vis[i]) continue;
        curcnt = 0;
        dfscheck(i,i);
        if(ok){poc = i; break;}
    }
    if(!ok){ans.popb(); return ans;}
    for(ll i = 1;i<=n;i++){
        if(dsu[i]==poc){
            dfscol2(i,xid,x);
            break;
        }
    }
    dfscol3(root,yid,y);
    for(ll i = 1;i<=n;i++){
        if(ans[i]==0) ans[i] = v[2].sc;
    }
    reverse(all(ans));
    ans.popb();
    reverse(all(ans));
    return ans;
}
/**
6 5 2 2 2
0 1
0 2
0 3
0 4
0 5

9 10 4 2 3
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6
**/

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