Submission #805498

#	Time	Username	Problem	Language	Result	Execution time	Memory
805498		Meloric	Split the Attractions (IOI19_split)	C++17	100 / 100	137 ms	18092 KiB

split

#include <bits/stdc++.h>
#define pb push_back
//#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define ub upper_bound
#define debug(x) cerr << "\n" << (#x) << " is " << (x) << endl;
 
using namespace std;
 
const int inf = 1e18;
 
void p(auto A){
	for(auto e : A)cout << e << ' ';
	cout << '\n';
}
 
struct edge{
	int u, v, use;
	edge(){
		use = 1;
	}
	int f(int a){
		if(a==u)return v;
		else return u;
	}
	array<int, 3> get(){
		return {u, v, use};
	}
};
 
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
	array<int, 3> col = {1, 2, 3};
	array<int, 3> siz = {a, b, c};
	sort(all(col), [&](int i, int j){return siz[i-1] < siz[j-1];});
	sort(all(siz));
	int m = p.size();
	
	vector<edge>E(m);
	vector<vector<int>> g(n);
	
	for(int i = 0; i< m; i++){
		int u = p[i];
		int v = q[i];
		g[u].pb(i);
		g[v].pb(i);
		E[i].v = v;
		E[i].u = u;
	}
	
	vector<int> vis(n);
	auto dfs1 = [&](auto&& self, int u, int par)->void{
		vis[u] = 1;
		for(auto e : g[u]){
			int v = E[e].f(u);
			if(v==par)continue;
			if(vis[v]){
				E[e].use = 0;
				continue;
			}
			self(self, v, u);
		}
	};
	dfs1(dfs1, 0, 0);
	
	vector<int> sz(n, 1);
	auto dfs2 = [&](auto&& self, int u, int par)->int{
		int ret = -1;
		int flag = 1;
		for(auto e : g[u])if(E[e].use){
			int v = E[e].f(u);
			if(v==par)continue;
			ret = max(ret, self(self, v, u));
			sz[u]+=sz[v];
			if(sz[v] > n/2)flag = 0;
		}
		if(n-sz[u] > n/2)flag = 0;
		if(flag)ret = u;
		return ret;
	};
	
	int root = dfs2(dfs2, 0, 0);
	
	//debug(root);
	
	vector<int>P(n, -1);
	
	auto find = [&](int u)->int{
		while(P[u] >= 0)u = P[u];
		return u;
	};
	
	int start = -1;
	
	for(int i = 0; i< n; i++)if(i != root && -P[i] >= siz[0])start = i;
	if(start ==-1)for(auto e : E){
		auto [u, v, use] = e.get();
		if(!use)continue;
		if(u == root)continue;
		if(v == root)continue;
		u = find(u);
		v = find(v);
		if(u == v)continue;
		if(P[u] > P[v])swap(u, v);
		P[u]+=P[v];
		P[v] = u;			
		if(-P[u] >= siz[0])start = u;
	}
	
	if(start == -1)for(auto& e : E){
			auto [u, v, use] = e.get();
			if(use)continue;
			if(u==root)continue;
			if(v==root)continue;
			u=find(u);
			v=find(v);
			if(u==v)continue;
			e.use = 1;
			if(P[u]>P[v])swap(u, v);
			P[u]+=P[v];
			P[v]=u;
			if(-P[u] >= siz[0])start = u;
	}
	
	vector<int>out(n);
	if(start == -1){
		return out;
	}
 
	if(-P[start] >= siz[1]){
		swap(col[0], col[1]);
		swap(siz[0], siz[1]);
	}
	
	vector<int>st;
	st.pb(start);
	while(siz[0]){
		assert(st.size());
		int u = st.back();
		st.pop_back();
		if(u == root)continue;
		if(out[u])continue;
		siz[0]--;
		out[u] = col[0];
		for(auto e : g[u])if(E[e].use)st.pb(E[e].f(u));
	}
	st.clear();
	st.pb(root);
	while(siz[1]){
		assert(st.size());
		int u = st.back();
		st.pop_back();
		if(out[u])continue;
		siz[1]--;
		out[u] = col[1];
		for(auto e : g[u])st.pb(E[e].f(u));
	}
	for(auto& e : out)if(!e)e=col[2];
	return out;
}
/*
void solve(){
	int n, m; cin >> n >> m;
	int a, b, c; cin >> a >> b >> c;
	vector<int>P(m), Q(m);
	for(int i = 0; i< m; i++)cin >> P[i] >> Q[i];
	vector<int> ans = find_split(n, a, b, c, P, Q);
	for(auto e : ans)cout << e << ' ';
}
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t = 1;
	//cin >> t;
	while(t--)solve();
}
*/

Compilation message (stderr)

split.cpp:14:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | const int inf = 1e18;
      |                 ^~~~
split.cpp:16:8: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | void p(auto A){
      |        ^~~~

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