Submission #722919

#	Time	Username	Problem	Language	Result	Execution time	Memory
722919		victor_gao	Split the Attractions (IOI19_split)	C++17	40 / 100	1730 ms	26616 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],tre[N],leaf1,leaf2,res;
int sz[N],A,B,C,deg[N],mx[N],n;
bool vis[N];
struct dsu{
	int arr[N],sz[N];
	void init(int n){
		for (int i=1;i<=n;i++){
			arr[i]=i; sz[i]=1;
		}
	}
	int find(int x){
		if (arr[x]==x) return x;
		return arr[x]=find(arr[x]);
	}
	void Merge(int a,int b){
		int ra=find(a),rb=find(b);
		if (ra==rb) return;
		if (sz[ra]<sz[rb]) swap(ra,rb);
		sz[ra]+=sz[rb];
		arr[rb]=ra;
	}
}dsu;
vector<pii>edge;
void build_tree(){
	shuffle(edge.begin(),edge.end(),rng);
	dsu.init(n);
	for (auto [u,v]:edge){
		if (dsu.find(u)!=dsu.find(v)){
			tre[u].emplace_back(v);
			tre[v].emplace_back(u);
			dsu.Merge(u,v);
		}
	}
}
void get_tree(int p){
	vis[p]=1;
	shuffle(g[p].begin(),g[p].end(),rng);
	for (auto i:g[p]){
		if (!vis[i]){
			tre[i].emplace_back(p);
			tre[p].emplace_back(i);
			get_tree(i);
		}
	}
}
void bfs_tree(int rt){
	queue<int>q; q.push(rt);
	vis[rt]=1;
	while (!q.empty()){
		int now=q.front(); q.pop();
		for (auto i:g[now]){
			if (!vis[i]){
				vis[i]=1;
				tre[now].emplace_back(i);
				tre[i].emplace_back(now);
				q.push(i);
			}
		}
	}
}
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];
		}
	}
	mx[p]=max(mx[p],(n-sz[p]));
}
void dfs1(int p,int lp){
	res[p]=1;
	if (tre[p].size()==1)
		leaf1.push_back(p);
	for (auto i:tre[p])
		if (i!=lp)
			dfs1(i,p);
}
void dfs2(int p,int lp){
	res[p]=2;
	if (tre[p].size()==1)
		leaf2.push_back(p);
	for (auto i:tre[p])
		if (i!=lp)
			dfs2(i,p);
}
void solve(){
	count_size(1,0);
	int mid=0;
	for (int i=1;i<=n;i++){
		if (mx[i]>=A&&n-mx[i]>=B){
			mid=i;
			break;
		}
		else if (mx[i]>=B&&n-mx[i]>=A){
			mid=i;
			break;
		}
	}
	if (mid==0) return;
	count_size(mid,0);
	vector<pii>all;
	for (auto i:tre[mid])
		all.push_back({sz[i],i});
	sort(all.begin(),all.end());
	int now1=0,now2=0;
	if (all.back().x>=B){
		dfs2(all.back().y,mid);
		now2=all.back().x;
		for (int i=0;i<all.size()-1;i++){
			dfs1(all[i].y,mid);
			now1+=all[i].x;
		}
		res[mid]=1; now1++;
	}
	else {
		dfs1(all.back().y,mid);
		now1=all.back().x;
		for (int i=0;i<all.size()-1;i++){
			dfs2(all[i].y,mid);
			now2+=all[i].x;
		}
		res[mid]=2; now2++;
	}
	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);
		}
	}
}
void reset(){
	fill(res.begin(),res.end(),0);
	leaf1.clear(); leaf2.clear();
	for (int j=1;j<=n;j++){
		tre[j].clear(); vis[j]=0;
		deg[j]=0; sz[j]=0;
	}
}
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++){
		edge.push_back({p[i]+1,q[i]+1});
		g[p[i]+1].push_back(q[i]+1);
		g[q[i]+1].push_back(p[i]+1);
	}
	res.resize(n+1);
	for (int i=1;i<=30;i++){
		reset();
		get_tree(rng()%n+1);
		solve();
		if (res[1]) break;
	}
	if (!res[1]){
		for (int i=1;i<=30;i++){
			reset();
			build_tree();
			solve();
			if (res[1]) break;
		}
	}
	if (!res[1]){
		for (int i=1;i<=30;i++){
			reset();
			bfs_tree(rng()%n+1);
			solve();
			if (res[1]) break;
		}
	}
	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);
	int sz[4]={};
	for (auto i:ans)
		sz[i]++;
	assert(sz[1]==a&&sz[2]==b&&sz[3]==c);
	return ans;
}

Compilation message (stderr)

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

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