Submission #352602

#	Time	Username	Problem	Language	Result	Execution time	Memory
352602		tengiz05	Split the Attractions (IOI19_split)	C++17	40 / 100	191 ms	25964 KiB

split

#include "split.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N = 1e5+5;
int n, m;
vector<int> edges[N];
vector<int> g[N];
bool used[N];
int subtree_size[N];
vector<pii> extra;
void Dfs(int u, int p=-1){
	used[u] = true;
	subtree_size[u] = 1;
	for(auto v : edges[u]){
		if(used[v]){
			if(v != p)extra.pb({u,v});
			continue;
		}
		g[u].pb(v);
		g[v].pb(u);
		Dfs(v,u);
		subtree_size[u] += subtree_size[v];
	}
}
int find_centroid(int u, int p){
	for(auto v : g[u]){
		if(v!=p && subtree_size[v] >= n/2)return find_centroid(v,u);
	}return u;
}
void recalc_size(int u, int p){
	subtree_size[u] = 1;
	for(auto v : g[u]){
		if(v == p)continue;
		recalc_size(v,u);
		subtree_size[u] += subtree_size[v];
	}
}

// start of DSU
vector<int> p, sz;
void Init(int n){
	p.assign(n,0);
	sz.assign(n,1);
	for(int i=0;i<n;i++)p[i]=i;
}
int par(int u){
	if(p[u] == u)return u;
	return p[u] = par(p[u]);
}
bool IsSame(int u, int v){
	return par(u) == par(v);
}
void merge(int u,int v){
	u=par(u);v=par(v);
	if(u == v)return;
	p[v] = u;
	sz[u] += sz[v];
	return;
}
int size_of_node(int u){
	return sz[par(u)];
}// end of DSU

pii sizes[3];
vector<int> ans;
int center;
int remaining;
void color(int u){
	used[u] = true;
	ans[u] = sizes[0].second;
	remaining--;
	if(not remaining)return;
	for(auto v : g[u]){
		if(not remaining)return;
		if(used[v] || v == center)continue;
		color(v);
	}
}

void colorB(int u){
	used[u] = true;
	ans[u] = sizes[1].second;
	remaining--;
	if(not remaining)return;
	for(auto v : edges[u]){
		if(not remaining)return;
		if(used[v])continue;
		colorB(v);
	}
}


vector<int> find_split(int N, int a, int b, int c, vector<int> P, vector<int> Q) {
	Init(N);
	sizes[0] = {a,1};
	sizes[1] = {b,2};
	sizes[2] = {c,3};
	sort(sizes,sizes+3);
	a = sizes[0].first;
	b = sizes[1].first;
	c = sizes[2].first;
	n=N; m = P.size();
	for(int i=0;i<m;i++){
		edges[P[i]].pb(Q[i]);
		edges[Q[i]].pb(P[i]);
	}
	ans.assign(n,sizes[2].second);
	Dfs(0);
	center = find_centroid(0,0);
	recalc_size(center,center);
	for(int u=0;u<n;u++){
		if(u == center)continue;
		for(auto v : g[u]){
			if(v != center)merge(u,v);
		}
	}for(auto u : edges[center]){
		if(size_of_node(u) >= a){
			// yay we found solution! (I hope)
			remaining = a;
			memset(used,0,sizeof used);
			color(u);
			remaining = b;
			colorB(center);
			return ans;
		}
	}
	for(auto [u, v] : extra){
		if(IsSame(u,v))continue;
		g[u].pb(v);
		g[v].pb(u);
		merge(u,v);
		for(auto u : edges[center]){
			if(size_of_node(u) >= a){
				// yay we found solution! (I hope)
				memset(used,0,sizeof used);
				remaining = a;
				color(u);
				assert(not remaining);
				remaining = b;
				colorB(center);
				assert(not remaining);
				return ans;
			}
		}
	}
	return vector<int>(n,0);
}

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