Submission #1028079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028079		Belphegor	Split the Attractions (IOI19_split)	C++14	100 / 100	81 ms	27104 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
const int sz = 500000;
vector<int>tree[sz+5];
int sub[sz+5],visited[sz+5],idx,cnt;
int DFS(int cur){
	sub[cur] = 1;
	for(int nxt : tree[cur]){
		if(!sub[nxt]) sub[cur]+=DFS(nxt);
	}
	return sub[cur];
}
void dfs(int cur,vector<int>&v){
	if(!cnt) return;
	visited[cur] = 1; v[cur] = idx; cnt--;
	for(int nxt : tree[cur]){
		if(!visited[nxt]) dfs(nxt,v);
	}
}
struct UF{
	vector<int>p;
	UF(int n){
		p = vector<int>(n+3,-1);
	}
	void init(){
		for(int i=0; i<p.size(); i++) p[i] = -1;
	}
	int f(int a){
		if(p[a] < 0) return a;
		return p[a] = f(p[a]);
	}
	void merge(int a,int b){
		a = f(a); b = f(b);
		if(a!=b){
			p[a]+=p[b];
			p[b] = a;
		}
	}
	int get_size(int x){
		x = f(x);
		return -p[x];
	}
};
vector<int> find_split(int n, int A, int B, int C, vector<int> p, vector<int> q) {
	vector<pi>ord;
	ord.emplace_back(pi(A,1));
	ord.emplace_back(pi(B,2));
	ord.emplace_back(pi(C,3));
	sort(ord.begin(),ord.end());
	vector<pi>edge;
	UF uf(n);
	for(int i=0; i<p.size(); i++){
		int a = p[i],b = q[i];
		if(uf.f(a) == uf.f(b)){
			edge.emplace_back(pi(a,b));
			continue;
		}
		uf.merge(a,b);
		tree[a].emplace_back(b);
		tree[b].emplace_back(a);
	}
	DFS(0);
	int cen = 0;
	while(1){
		int mx = 0,child = -1;
		for(int nxt : tree[cen]){
			if(sub[nxt] > sub[cen]) continue;
			if(sub[nxt] > mx){
				mx = sub[nxt];
				child = nxt;
			}
		}
		if(mx > n/2) cen = child;
		else break;
	}
	//c is centroid
	uf.init();
	for(int i=0; i<n; i++){
		for(int nxt : tree[i]){
			if(i == cen || nxt == cen) continue;
			uf.merge(i,nxt);
		}
	}
	int s = -1;
	for(int i=0; i<n; i++){
		if(i == cen) continue;
		if(uf.get_size(i) >= ord[0].first) s = i;
	}
	if(s<0){
		for(pi px : edge){
			int a = px.first,b = px.second;
			if(a == cen || b == cen) continue;
			tree[a].emplace_back(b);
			tree[b].emplace_back(a);
			uf.merge(a,b);
			if(uf.get_size(a) >= ord[0].first) s = a;
			if(uf.get_size(b) >= ord[0].first) s = b;
			if(s >= 0) break;
		}
	}
	if(s<0){return vector<int>(n,0);}
	
	vector<int>v = vector<int>(n,ord[2].second);
	visited[cen] = 1;
	idx = ord[0].second; cnt = ord[0].first; dfs(s,v);
	visited[cen] = 0;
	idx = ord[1].second; cnt = ord[1].first; dfs(cen,v);
	return v;
}

Compilation message (stderr)

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

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