Submission #536671

#	Time	Username	Problem	Language	Result	Execution time	Memory
536671		zggf	Split the Attractions (IOI19_split)	C++14	29 / 100	156 ms	44108 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> graf;
vector<vector<int>> tree;
vector<int> sz;
vector<int> odw;

void dfs(int x){
	odw[x] = true;
	sz[x] = 1;
	for(auto it:graf[x]){
		if(!odw[it]){
			tree[x].push_back(it);
			tree[it].push_back(x);
			dfs(it);
			sz[x]+=sz[it];
		}
	}
}

int centroid(int x){
	odw[x] = true;
	for(auto it:tree[x]){
		if(odw[it]) continue;
		if(sz[x]-sz[it]<sz[it]){
			int tmp = sz[it];
			sz[it] = sz[x];
			sz[x] = sz[x]-tmp;	
			return centroid(it);
		}
	}
	return x;
}

vector<int> kolor;
int curKolor=1;

void dfs2(int x){
	kolor[x] = curKolor;	
	for(auto it:tree[x]){
		if(kolor[it]==0){
			dfs2(it);
		}
	}
}

vector<vector<int>> graf2;
vector<int> waga;

void dfs3(int x){
	odw[x] = true;
	for(auto it:graf[x]){
		if(!odw[it]){
			if(kolor[it]==kolor[x]){
				dfs3(it);
			}else{
				if(kolor[it]!=-1){
					graf[kolor[it]].push_back(kolor[x]);
					graf[kolor[x]].push_back(kolor[it]);
				}
			}
		}
	}
}

vector<bool> odw2;
int A;
int suma = 0;

void dfs4(int x){
	odw2[x] = true;
	suma+=waga[x];
	if(suma>=A) return;
	for(auto it:graf2[x]){
		if(!odw2[it]){
			dfs4(it);
			if(suma>=A) return;
		}
	}
}
bool curOdw = true;
int suma2 = 0;
int curSuma = 0;
vector<int> wynik;

void dfs5(int x){
	//cout<<x<<'\n';
	odw[x] = true;
	wynik[x] = 2-curOdw;
	suma2++;
	if(suma2>=curSuma) return;
	for(auto it:graf[x]){
		if(!odw[it]){
			if(curOdw){
				if(kolor[it]==-1) continue;
				if(odw2[kolor[it]]==curOdw){
					dfs5(it);
					if(suma2>=curSuma) return;
				}
			}else{
				dfs5(it);
				if(suma2>=curSuma) return;
			}
		}
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {

	A = min(min(c, b), a);
	graf.resize(n);
	odw.resize(n);
	sz.resize(n);
	tree.resize(n);
	for(int i = 0; i < (int)p.size(); i++){
		graf[p[i]].push_back(q[i]);
		graf[q[i]].push_back(p[i]);
	}
	dfs(0);
	odw.resize(0);
	odw.resize(n);
	int cent = centroid(0);
	kolor.resize(n);
	kolor[cent] = -1;
	waga.resize(n);
	graf2.resize(n);
	for(auto it:tree[cent]){
		waga[curKolor] = sz[it];
		dfs2(it);
		curKolor++;
	}
	odw.resize(0);
	odw.resize(n);
	for(auto it:tree[cent]){
		dfs3(it);
	}
	for(auto it:tree[cent]){
		odw2.resize(n);
		dfs4(kolor[it]);
		if(suma>=A) break;
		odw2.resize(0);
		suma=0;
	}
	wynik.resize(n, 0);
	if(suma==0){
		return wynik;		
	}
	curOdw = true;
	curSuma = A;
	suma2=0;
	odw.resize(0);
	odw.resize(n);
	for(auto it:tree[cent]){
		if(odw2[kolor[it]]==curOdw){
			dfs5(it);
			break;
		}
	}
	curOdw = false;
	curSuma = a+b+c-A-max(a, max(b, c));
	//cout<<curSuma<<'\n';
	suma2=0;
	dfs5(cent);
	vector<pair<int, int>> conv;
	conv.push_back({a, 1});
	conv.push_back({b, 2});
	conv.push_back({c, 3});
	sort(conv.begin(), conv.end());

	for(int i = 0; i < (int)wynik.size(); i++){
		if(wynik[i]==0) wynik[i] = conv[2].second;
		else if(wynik[i]==1) wynik[i] = conv[0].second;
		else if(wynik[i]==2) wynik[i] = conv[1].second;
	}
	
	return wynik;
}

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