Submission #725891

#	Time	Username	Problem	Language	Result	Execution time	Memory
725891		victor_gao	Split the Attractions (IOI19_split)	C++17	33 / 100	218 ms	73804 KiB

split

#pragma GCC optimize("Ofast,unroll-loops")
#include "split.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int>g[N],leaf1,leaf2,res;
vector<pii>change,need_in;
set<int>tre[N];
int sz[N],n,a,b,c,mx[N],deg[N],fa[N];
int now1,now2,t=0,dfn[N],idx[2*N];
pii low[N];
bool vis[N];
void dfs(int p,int c){
	vis[p]=1;
	for (auto i:g[p]){
		if (res[i]==c&&!vis[i])
			dfs(i,c);
	}
}
bool checker(){
	int have[5]={0};
	for (int i=1;i<=n;i++){
		if (!vis[i]){
			dfs(i,res[i]);
			have[res[i]]++;
		}
	}
	int h=(have[1]>1)+(have[2]>1)+(have[3]>1);
	cout<<h<<'\n';
	return h<=1;
}
void get_tree(int p,int lp){
	fa[p]=lp; dfn[p]=++t; idx[dfn[p]]=p;
	low[p]=pii(dfn[p],p);
	//cout<<"tree : "<<p-1<<" "<<lp-1<<'\n';
	for (auto i:g[p]){
		if (!dfn[i]){
			tre[i].insert(p);
			tre[p].insert(i);
			get_tree(i,p);
			low[p]=min(low[p],low[i]);
		}
		else if (i!=lp&&dfn[i]<dfn[p])
			low[p]=min(low[p],pii(dfn[i],p));
	}
}
void count_size(int p,int lp){
	sz[p]=1; deg[p]=tre[p].size(); mx[p]=0;
	for (auto i:tre[p]){
		if (i!=lp){
			count_size(i,p);
			mx[p]=max(mx[p],sz[i]);
			sz[p]+=sz[i];
		}
	}
}
void dfs1(int p,int lp){
	res[p]=1; now1++;
	if (tre[p].size()==1)
		leaf1.push_back(p);
	for (auto i:tre[p])
		if (i!=lp&&!res[i])
			dfs1(i,p);
}
void dfs2(int p,int lp){
	res[p]=2; now2++;
	if (tre[p].size()==1)
		leaf2.push_back(p);
	for (auto i:tre[p])
		if (i!=lp&&!res[i])
			dfs2(i,p);
}
bool check(int i){
	if (sz[i]>=a&&sz[i]<=n-a)
		return 1;
	vector<pii>all;
	for (auto j:tre[i]){
		if (j!=fa[i]&&low[j].x<dfn[i])
			all.push_back({sz[j],j});
	}
	sort(all.begin(),all.end());
	change.clear();
	int now=sz[i];
//	cout<<"check "<<i<<" -> \n";
	for (auto [s,j]:all){
		now-=s;
		change.push_back({i,j});
		need_in.push_back(pii(low[j].y,idx[low[j].x]));
	//	cout<<"OUT "<<j<<" "<<s<<'\n';
		if (now>=a&&now<=n-a){
	//		cout<<i<<" find "<<now<<'\n';
			for (auto [a,b]:change){
				tre[a].erase(b);
				tre[b].erase(a);
			}
			sz[i]=now;
			return 1;
		}
	}
	return 0;
}
void solve(){
	count_size(1,0);
	int mid=0;
	for (int i=1;i<=n;i++){
		if (check(i)){
			mid=i;
			break;
		}
	}
	if (mid==0) return;
//	cout<<mid<<" size is : "<<sz[mid]<<'\n';
	if (sz[mid]>=b){
		dfs2(mid,fa[mid]);
		for (auto [a,b]:need_in){
			tre[a].insert(b);
			tre[b].insert(a);
		}
		for (auto i:tre[mid])
			if (!res[i])
				dfs1(i,mid);
	}
	else {
		dfs1(mid,fa[mid]);
		for (auto [a,b]:need_in){
			tre[a].insert(b);
			tre[b].insert(a);
		}
		for (auto i:tre[mid])
			if (!res[i])
				dfs2(i,mid);
	}
	//for (int i=1;i<=n;i++)
//		cout<<res[i]<<" ";
	//cout<<'\n';
	while (now1>a){
		int out=leaf1.back(); leaf1.pop_back();
		res[out]=3; now1--;
		for (auto i:tre[out]){
			deg[i]--;
			if (deg[i]==1)
				leaf1.push_back(i);
		}
	}
	while (now2>b){
		int out=leaf2.back(); leaf2.pop_back();
		res[out]=3; now2--;
		for (auto i:tre[out]){
			deg[i]--;
			if (deg[i]==1)
				leaf2.push_back(i);
		}
	}
}
vector<int> find_split(int _n, int A, int B, int C, vector<int> p, vector<int> q) {
	n=_n;
	vector<pii>s={{A,1},{B,2},{C,3}};
	sort(s.begin(),s.end());
	a=s[0].x; b=s[1].x; c=s[2].x;
	for (int i=0;i<p.size();i++){
		g[p[i]+1].push_back(q[i]+1);
		g[q[i]+1].push_back(p[i]+1);
	}
	res.resize(n+1);
	get_tree(1,0); solve();
	//checker();
	vector<int>ans; ans.resize(n,0);
	if (res[1]==0) return ans;
	for (int i=1;i<=n;i++)
		ans[i-1]=(s[res[i]-1].y);
	return ans;
}
/*
13 17 2 2 9
1 0
2 0
3 0
4 0
5 1
6 4
7 1
8 3
9 7
10 1
11 4
12 1
6 2
9 8
6 7
8 7
4 3

*/

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:164:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |  for (int i=0;i<p.size();i++){
      |               ~^~~~~~~~~

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