Submission #686576

#	Time	Username	Problem	Language	Result	Execution time	Memory
686576		urosk	Split the Attractions (IOI19_split)	C++14	18 / 100	81 ms	15004 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define here cerr<<"============================================\n"
#define ll long long
#define llinf 1000000000000LL
#define sz(a) (ll)(a.size())
#define pb push_back
#define all(a) a.begin(),a.end()
#define popb pop_back
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}

using namespace std;
#define maxn 100005
ll n,m;
vector<ll> g[maxn];
ll x,y,z;
ll col[maxn];
ll siz[maxn],sizmx[maxn],par[maxn];
void dfs1(ll u){
    if(!y) return;
    col[u] = 2;
    y--;
    for(ll s : g[u]) if(!col[s]) dfs1(s);
}
void dfs2(ll u){
    if(x) col[u] = 1,x--;
    else if(y) col[u] = 2,y--;
    else col[u] = 3,z--;
    for(ll s : g[u]) if(!col[s]) dfs2(s);
}
ll nod = -1; bool f;
ll dfssiz(ll u,ll p){
    siz[u] = 1;
    par[u] = p;
    for(ll s : g[u]){
        if(s!=p){
            dfssiz(s,u);
            siz[u]+=siz[s];
            sizmx[u] = max(sizmx[s],sizmx[u]);
        }
    }
    if(nod==-1){
        if(siz[u]>=x&&n-siz[u]>=y){
            nod = u; f = 1;
        }else if(siz[u]>=y&&n-siz[u]>=x){
            nod = u; f = 0;
        }
    }
    return siz[u];
}
void dfscol(ll u,ll w){
    if(!col[u]){
        if((f==1)&&(x>0)){
            col[u] = 1;
            x--;
        }
        else if((f==0)&&(y>0)){
            col[u] = 2; y--;
        }
        else col[u] = 3;
    }
    for(ll s : g[u]){
        if(s==w) continue;
        if(col[s]) continue;
        dfscol(s,w);
    }
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
    n = N;
    m = sz(p);
    x = A,y = B,z = C;
    for(ll i = 0;i<m;i++){
        ll x = p[i],y = q[i];
        x++; y++;
        g[x].pb(y);
        g[y].pb(x);
    }
    ll mxdeg = 0,mndeg = llinf;
    for(ll i = 1;i<=n;i++) mxdeg = max(mxdeg,sz(g[i]));
    for(ll i = 1;i<=n;i++) mndeg = min(mndeg,sz(g[i]));
    if(mxdeg<=2){
        ll poc = 1;
        if(mndeg==1){
            for(ll i = 1;i<=n;i++) if(sz(g[i])==1) poc = i;
        }
        dfs2(poc);
        vector<int> ans(n);
        for(ll i = 1;i<=n;i++) ans[i-1] = col[i];
        return ans;
    }
    if(x==1){
        dfs1(1);
        for(ll i = 1;i<=n;i++){
            if(col[i]) continue;
            if(x){
                col[i] = 1;
                x--;
            }else col[i] = 3;
        }
        vector<int> ans(n);
        for(ll i = 1;i<=n;i++) ans[i-1] = col[i];
        return ans;
    }
    if(m==n-1){
        vector<ll> w = {A,B,C}; sort(all(w)); x = w[0],y = w[1],z = w[2];
        dfssiz(1,1);
        vector<int> ans(n);
        if(nod==-1) return ans;
        for(ll i = 1;i<=n;i++) col[i] = 0;
        dfscol(nod,par[nod]);
        f^=1;
        dfscol(nod,0);
        vector<ll> cur(4);
        for(ll i = 1;i<=n;i++) if(!col[i]) col[i] = 3;
        for(ll i = 1;i<=n;i++) cur[col[i]]++;
        for(ll i = 1;i<=n;i++) ans[i-1] = col[i];
        return ans;
    }
	return {};
}

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