Submission #1034168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034168		amirhoseinfar1385	Split the Attractions (IOI19_split)	C++17	33 / 100	59 ms	23256 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
vector<int>adj[maxn];
int high[maxn],sz[maxn];
int n,a,b,c,rt,m,f=0,res[maxn],vis[maxn],s,t,bal[maxn],timea;
vector<pair<int,int>>allv;
pair<int,int>stf[maxn];

bool zird(int u,int v){
	return stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second;
}

void clear(){
	for(int i=0;i<=n;i++){
		vis[i]=0;
		sz[i]=high[i]=0;
		stf[i]=make_pair(0,0);
		bal[i]=0;
	}
}

void dfs(int u,int par=-1){
	timea++;
	stf[u].first=timea;
	vis[u]=1;
	bal[u]=high[u];
	sz[u]=1;
	for(auto x:adj[u]){
		if(x==par||vis[x]==0){
			continue;
		}
		bal[u]=min(bal[u],high[x]);
	}
	long long suma=0,z=0;
	for(auto x:adj[u]){
		if(vis[x]==0){
			high[x]=high[u]+1;
			dfs(x,u);
			sz[u]+=sz[x];
			bal[u]=min(bal[u],bal[x]);
			if(bal[x]>=high[u]){
				f=1;
				z=1;
				if(sz[x]>=a&&n-sz[x]>=b){
					s=x;
					t=u;
				}
				if(sz[x]>=b&&(n-sz[x])>=a){
					s=u;
					t=x;
				}
			}else{
				suma++;
			}
		}
	}
	if(z==1&&s==-1){
		if(suma>=a&&n-suma>=b){
			rt=u;
		}
		if(suma>=b&&(n-suma)>=a){
			rt=u;
		}
	}
	stf[u].second=timea;
}

void dfssolve(int u,int nar,int w,int ww=0){
	if(a==0){
		return ;
	}
	a--;
	res[u]=w;
	vis[u]=1;
	for(auto x:adj[u]){
		if(ww==1&&zird(x,nar)){
			continue;
		}
		if(x==nar||vis[x]){
			continue;
		}
		dfssolve(x,nar,w,ww);
	}
}

vector<int>rasbor(){
	f=0;
	dfs(0);
	if(f==0){
		return {};
	}
	clear();
	dfs(rt);
	//cout<<s<<" "<<t<<endl;
	if(f==1&&s==-1&&rt==-1){
		vector<int>ret;
		ret.resize(n);
		return ret;
	}
	clear();
	//cout<<s<<" "<<t<<" "<<high[s]<<" "<<high[t]<<endl;
	dfssolve(s,t,1,(high[s]<high[t]));
	clear();
	swap(a,b);
	dfssolve(t,s,2,(high[t]<high[s]));
	vector<int>ret;
	for(int i=0;i<n;i++){
		if(res[i]>=1){
			ret.push_back(res[i]);
		}else{
			ret.push_back(3);
		}
	}
	return ret;
}

vector<int>doham(){
	vector<int>ret;
	int cnt=0;
	priority_queue<pair<int,int>>pq;
	pq.push(make_pair(high[0],0));
	for(int i=0;i<a;i++){
		auto x=pq.top();
		pq.pop();
		if(res[x.second]==1){
			i--;
			continue;
		}
		res[x.second]=1;
		for(auto y:adj[x.second]){
			pq.push(make_pair(high[y],y));
		}
	}
	for(int i=0;i<n;i++){
		if(res[i]==1){
			continue;
		}
		if(cnt<b){
			res[i]=2;
			cnt++;
		}else{
			res[i]=3;
		}
	}
	for(int i=0;i<n;i++){
		if(res[i]>=1){
			ret.push_back(res[i]);
		}else{
			ret.push_back(3);
		}
	}
	return ret;
}

vector<int>solve(){
	vector<int>ret=rasbor();
	if(ret.size()==0){
		ret=doham();
	}
	for(int i=0;i<n;i++){
		if(ret[i]!=0)
		ret[i]=allv[ret[i]-1].second;
	}	
	return ret;
}

vector<int> find_split(int n_, int a_, int b_, int c_, vector<int> p, vector<int> q) {
	n=n_;
	rt=-1;
	s=t=-1;
	allv.push_back(make_pair(a_,1));
	allv.push_back(make_pair(b_,2));
	allv.push_back(make_pair(c_,3));
	sort(allv.begin(),allv.end());
	a=allv[0].first;
	b=allv[1].first;
	c=allv[2].first;
	m=(int)p.size();
	for(int i=0;i<m;i++){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	//solve();
	return solve();
}

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