Submission #144514

#	Time	Username	Problem	Language	Result	Execution time	Memory
144514		Lyestria	Split the Attractions (IOI19_split)	C++14	100 / 100	169 ms	18660 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
const int mn=2e5+10;
int p[mn],si[mn];
inline int f(int x){return x==p[x]?x:(p[x]=f(p[x]));}
inline int siz(int x){return si[f(x)];}
void mrg(int a,int b){a=f(a),b=f(b);if(a==b);else if(si[a]>si[b])si[a]+=si[b],p[b]=a;else si[b]+=si[a],p[a]=b;}
void init(){iota(p,p+mn,0);fill(si,si+mn,1);}
bool u[mn];
vector<int>g[mn],ans;
int s[mn];
int ctr,n;
void dfs(int x,int p){
    s[x]=1;
    for(int y:g[x]){
        if(y==p)continue;
        dfs(y,x);
        s[x]+=s[y];
    }
}
int fc(int x,int p){
    for(int y:g[x]){
        if(y==p)continue;
        if(s[y]*2>=n)return fc(y,x);
    }
    return x;
}
void dfs2(int x,int p){
    for(int y:g[x]){
        if(y==p)continue;
        dfs2(y,x);
        mrg(x,y);
    }
}
int lef,tar;
bool vis[mn];
int conv[4];
void dfs3(int x){
    if(!lef)return;
    vis[x]=1;
    lef--;
    ans[x]=conv[tar];
    for(int y:g[x]){
        if(!vis[y]){
            dfs3(y);
            if(!lef)return;
        }
    }
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
    int sm=min(a,min(b,c)),bi=max(a,max(b,c));
    if(a==sm)conv[1]=1;
    else if(a==bi)conv[3]=1;
    else conv[2]=1;
    if(b==sm&&!conv[1])conv[1]=2;
    else if(b==bi&&!conv[3])conv[3]=2;
    else conv[2]=2;
    if(c==sm&&!conv[1])conv[1]=3;
    else if(c==bi&&!conv[3])conv[3]=3;
    else conv[2]=3;
    b=a+b+c-sm-bi;
    a=sm;
    c=bi;
    n=N;
    ans.resize(n,conv[3]);
	int m=p.size(),i;
	init();
	for(i=0;i<m;i++){
        if(f(p[i])!=f(q[i])){
            mrg(p[i],q[i]);
            g[p[i]].push_back(q[i]);
            g[q[i]].push_back(p[i]);
        }
	}
	dfs(0,-1);
	ctr=fc(0,-1);
	init();
    for(int y:g[ctr]){
        dfs2(y,ctr);
        if(siz(y)>=a){
            vis[ctr]=1;
            lef=a;
            tar=1;
            dfs3(y);
            lef=b;
            tar=2;
            vis[ctr]=0;
            dfs3(ctr);
            return ans;
        }
    }
    for(i=0;i<m;i++){
        if(p[i]==ctr||q[i]==ctr)continue;
        if(f(p[i])==f(q[i]))continue;
        mrg(p[i],q[i]);
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
        if(siz(p[i])>=a){
            vis[ctr]=1;
            lef=a;
            tar=1;
            dfs3(p[i]);
            lef=b;
            tar=2;
            vis[ctr]=0;
            dfs3(ctr);
            return ans;
        }
    }
    fill(ans.begin(),ans.end(),0);
    return ans;
}

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