Submission #198501

#	Time	Username	Problem	Language	Result	Execution time	Memory
198501		Akashi	Split the Attractions (IOI19_split)	C++14	40 / 100	226 ms	27764 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

const int SZ = 2e5 + 5;

vector <int> v[SZ];

int n;
int d[SZ], Max[SZ], TT[SZ];
bool viz[SZ];

void dfs(int nod){
	viz[nod] = 1; d[nod] = 1;
	for(auto it : v[nod]){
		if(viz[it]) continue ;
		TT[it] = nod;
		dfs(it);
		d[nod] += d[it];
		Max[nod] = max(Max[nod], d[it]);
	}
}

int find_centroid(int nod){
	viz[nod] = 1;
	
	if(max(Max[nod], n - d[nod]) <= n / 2) return nod;
	
	for(auto it : v[nod]){
		if(viz[it]) continue ;
		int x = find_centroid(it);
		if(x) return x;
	}
	
	return 0;
}

vector <int> comp[SZ];
int id[SZ], RG[SZ];

inline int find(int x){
	int R = x;
	while(R != id[R]) R = id[R];
	
	while(id[x] != R){
		int aux = id[x];
		id[x] = R;
		x = aux;
	}
	return R;
}

inline void unite(int x, int y){
	if(x == y) return ;
	if(RG[x] >= RG[y]) id[y] = x, RG[x] += RG[y];
	else id[x] = y, RG[y] += RG[x];
}

void make_comp(int nod, int NR){
	comp[NR].push_back(nod);
	
	viz[nod] = 1;
	for(auto it : v[nod]){
		if(viz[it]) continue ;
		unite(find(it), find(nod));
		make_comp(it, NR);
	}
}

bool merge_comp(int nod, int &am, int a){
	viz[nod] = 1;
	for(auto it : v[nod]){
		if(viz[it]) continue ;
		if(find(it) == find(nod)) merge_comp(it, am, a);
		else{
			unite(find(nod), find(it));
			am = RG[find(nod)];
			if(am >= a) return 1;
			merge_comp(it, am, a);
		}
	}
	return 0;
}

int cul[SZ];
void paint_comp(int nod, int &rem, int c){
	if(rem == 0) return ;
	viz[nod] = 1;
	--rem;
	cul[nod] = c;
	
	for(auto it : v[nod]){
		if(viz[it] || cul[it] || find(it) != find(nod)) continue ;
		if(rem) paint_comp(it, rem, c);
	}
}

vector<int> res;
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N;
	res.resize(n);
	int m = p.size();
	for(int i = 0; i < m ; ++i){
		v[p[i] + 1].push_back(q[i] + 1);
		v[q[i] + 1].push_back(p[i] + 1);
	}
		
	int ca = 1, cb = 2, cc = 3;
	if(a > b) swap(a, b), swap(ca, cb);
	if(a > c) swap(a, c), swap(ca, cc);
	if(b > c) swap(b, c), swap(cb, cc);
	
	for(int i = 1; i <= n ; ++i) id[i] = i, RG[i] = 1;
	
	dfs(1);
	memset(viz, 0, sizeof(viz));
	int nod = find_centroid(1);
	memset(viz, 0, sizeof(viz));
	dfs(nod);
	
	memset(viz, 0, sizeof(viz));
	int NR = 0;
	viz[nod] = 1;
	for(auto it : v[nod]){
		make_comp(it, NR);
		NR++;
	}
	
	bool found = false;
	int wh = 0;
	for(int i = 0; i < NR ; ++i){
		if(comp[i].size() >= a){
			found = true;
			wh = comp[i][0];
			break ;
		}
	}
	
	////cerr << found << endl;
	if(!found){
		memset(viz, 0, sizeof(viz));
		viz[nod] = 1;
		for(int i = 0; i < NR ; ++i){
			int x = comp[i].size();
			bool ok = merge_comp(comp[i][0], x, a);
			if(ok){
				wh = comp[i][0];
				break ;
			}
		}
	}
	
	if(wh == 0) return res;
	
	memset(viz, 0, sizeof(viz));
	viz[nod] = 1;
	paint_comp(wh, a, ca);
	for(int i = 1; i <= n ; ++i) unite(find(i), find(wh));
	memset(viz, 0, sizeof(viz));
	paint_comp(nod, b, cb);
	
	for(int i = 0; i < n ; ++i){
		if(cul[i + 1] == 0) cul[i + 1] = cc; 
		res[i] = cul[i + 1];
	}
	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:132:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(comp[i].size() >= a){
      ~~~~~~~~~~~~~~~^~~~

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