Submission #242509

#	Time	Username	Problem	Language	Result	Execution time	Memory
242509		thebes	Split the Attractions (IOI19_split)	C++14	100 / 100	271 ms	26296 KiB

split

#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;

namespace output{
    void __(short x){cout<<x;}
    void __(unsigned x){cout<<x;}
    void __(int x){cout<<x;}
    void __(long long x){cout<<x;}
    void __(unsigned long long x){cout<<x;}
    void __(double x){cout<<x;}
    void __(long double x){cout<<x;}
    void __(char x){cout<<x;}
    void __(const char*x){cout<<x;}
    void __(const string&x){cout<<x;}
    void __(bool x){cout<<(x?"true":"false");}
    template<class S,class T>
    void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");}
    template<class T>
    void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class S,class T>
    void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    void pr(){cout<<"\n";}
    template<class S,class... T>
    void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);}
}

using namespace output;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,char> pic;
typedef pair<double,double> pdd;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;

#define pb push_back
#define fox(i,x,y) for(int i=(x);i<=(y);i++)
#define foxr(i,x,y) for(int i=(y);i>=(x);i--)
#define F first
#define S second

const int MN = 1e5+5, MM = 2e5+5;
int N, M, A, B, C, i, j, use[MM], sz[MN], mx[MN], vs[MN], ds[MN], cc[MN], ct, rem;
vi tree[MN], ans;
vector<pii> adj[MN], hm;
int fnd(int x){return ds[x]=x==ds[x]?x:fnd(ds[x]);}

void dfs(int n){
    vs[n] = 1;
    for(auto v : adj[n]){
        if(!vs[v.F]){
            use[v.S]=1;
            dfs(v.F);
            tree[n].pb(v.F);
            tree[v.F].pb(n);
        }
    }
}

void dfs2(int n,int p){
    sz[n]=1; mx[n]=0;
    for(auto v : tree[n]){
        if(v==p) continue;
        dfs2(v, n);
        sz[n] += sz[v];
        mx[n] = max(mx[n], sz[v]);
    }
}

void dfs3(int n,int p){
    if(2*mx[n]<=N&&2*(N-sz[n])<=N) ct=n;
    for(auto v : tree[n]){
        if(v==p) continue;
        dfs3(v, n);
    }
}

void go(int n,int p){
    cc[fnd(n)]++;
    for(auto v : tree[n]){
        if(v==p) continue;
        ds[v] = ds[n];
        go(v, n);
    }
}

void mrk(int n,int g,int id,bool wew=false){
    vs[n] = 1;
    if(rem){
        ans[n]=id; rem--;
        for(auto v : adj[n]){
            if(!wew&&fnd(v.F)==g&&!vs[v.F]&&rem) mrk(v.F,g,id);
            if(wew&&fnd(v.F)!=g&&!vs[v.F]&&rem) mrk(v.F,g,id,wew);
        }
    }
}

vi find_split(int n,int a,int b,int c,vi p,vi q){
    N = n; M = (int)p.size();
    int w[]={1,2,3};
    A=a, B=b, C=c;
    ans.resize(N);
    if(A>B) swap(A,B), swap(w[0],w[1]);
    if(A>C) swap(A,C), swap(w[0],w[2]);
    if(B>C) swap(B,C), swap(w[1],w[2]);
    for(i=0;i<M;i++){
        adj[p[i]].pb({q[i],i});
        adj[q[i]].pb({p[i],i});
    }
    dfs(1);
    dfs2(1,-1);
    dfs3(1,-1);
    dfs2(ct,-1);
    ds[ct]=ct;
    for(auto v : tree[ct]){
        ds[v] = v;
        go(v, ct);
    }
    memset(vs,0,sizeof(vs));
    for(i=0;i<N;i++){
        if(cc[i]>=A){
            if(cc[i]>=B){
                rem = B;
                mrk(i,i,w[1]);
                rem = A;
                mrk(ct,i,w[0],1);
            }
            else{
                rem = A;
                mrk(i,i,w[0]);
                rem = B;
                mrk(ct,i,w[1],1);
            }
            for(auto &v : ans){
                if(!v) v=w[2];
            }
            return ans;
        }
    }
    for(i=0;i<M;i++){
        if(use[i]) continue;
        int x=p[i], y=q[i];
        if(x==ct||y==ct) continue;
        if(fnd(x)!=fnd(y)){
            x=fnd(x), y=fnd(y);
            cc[x] += cc[y];
            ds[y] = x;
            if(cc[x]>=A){
                if(cc[x]>=B){
                    rem = B;
                    mrk(x,x,w[1]);
                    rem = A;
                    mrk(ct,x,w[0],1);
                }
                else{
                    rem = A;
                    mrk(x,x,w[0]);
                    rem = B;
                    mrk(ct,x,w[1],1);
                }
                for(auto &v : ans){
                    if(!v) v=w[2];
                }
                return ans;
            }
        }
    }
    return ans;
}

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