제출 #538289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538289		jamezzz	Split the Attractions (IOI19_split)	C++17	18 / 100	156 ms	16676 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;

#define maxn 100005

int a,b,c,rem,col,mark[3],sub[maxn],s1,s2,cut,flag[maxn],vis[maxn];
bool backedge[maxn];
vector<int> res;
vector<int> AL[maxn];
vector<ii> x;

void dfs(int u,int p){
	sub[u]=1;
	for(int v:AL[u]){
		if(sub[v]!=0)continue;
		dfs(v,u);
		sub[u]+=sub[v];
	}
}

bool dfs2(int u,int p){
	bool res=false;
	vis[u]=true;
	for(int v:AL[u]){
		if(v==p)continue;
		if(sub[v]>sub[u]){//back edge
			if(s1-sub[u]>=a){
				s1-=sub[u];
				s2+=sub[u];
				flag[u]=1;
				return false;
			}
			else{
				return true;
			}
		}
		if(vis[v])continue;
		else res=res||dfs2(v,u);
	}
	return res;
}

void dfs3(int u,int oflag){
	vis[u]=true;
	//pf("flag[%d]: %d\n",u,flag[u]);
	if(flag[u]!=-1)oflag=flag[u];
	if(x[oflag].fi!=0){
		res[u]=x[oflag].se;
		//pf("res[%d]:=%d\n",u,x[oflag].se);
		--x[oflag].fi;
	}
	else{
		res[u]=x[2].se;
		//pf("res[%d]:=%d\n",u,x[2].se);
	}
	for(int v:AL[u]){
		if(sub[v]>sub[u])continue;
		if(vis[v])continue;
		dfs3(v,oflag);
	}
}

vector<int> find_split(int n,int _a,int _b,int _c,vector<int> p,vector<int> q){
	a=_a;b=_b;c=_c;
	x.pb({a,1});x.pb({b,2});x.pb({c,3});
	sort(all(x));
	//for(ii pr:x)pf("(%d %d) ",pr.fi,pr.se);pf("\n");
	for(int i=0;i<3;++i)mark[i]=x[i].se;
	tie(a,b,c)={x[0].fi,x[1].fi,x[2].fi};
	
	res.resize(n);
	for(int i=0;i<sz(p);++i){
		AL[p[i]].pb(q[i]);
		AL[q[i]].pb(p[i]);
	}
	dfs(0,-1);
	
	//for(int i=0;i<n;++i)pf("%d ",sub[i]);pf("\n");
	
	cut=-1;
	for(int u=1;u<n;++u){
		bool can=true;
		if(sub[u]<a)can=false;
		for(int v:AL[u]){
			if(sub[v]<sub[u]&&sub[v]>=a)can=false;
		}
		if(can){
			cut=u;break;
		}
	}
	if(cut==-1)return res;
	
	//pf("%d\n",cut);
	
	s1=sub[cut],s2=n-sub[cut];
	
	memset(flag,-1,sizeof flag);
	
	if(dfs2(cut,-1)){
		//pf("case 1\n");
		flag[cut]=0;//a
		memset(vis,0,sizeof vis);
		dfs3(0,1);//b
		//pf("%d\n",x[0].fi);
		for(int i=0;i<n;++i){
			if(res[i]!=x[2].se)continue;
			bool con=false;
			for(int j:AL[i]){
				if(res[j]==x[0].se)con=true;
			}
			if(con&&x[0].fi!=0){
				res[i]=x[0].se;
				--x[0].fi;
			}
		}
	}
	else{
		//pf("case 2\n");
		if(s2>a){
			for(int i=0;i<n;++i)if(flag[i]==1)flag[i]=0;//a
			flag[cut]=1;//b
			memset(vis,0,sizeof vis);
			dfs3(0,0);//a
		}
		else return res;
	}
	
	return res;
}

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