Submission #1064199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064199		jamjanek	Split the Attractions (IOI19_split)	C++14	100 / 100	97 ms	30144 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
bool odw[100010];
vector<int>graf[100010];
int a, b, c, n;
int low[100010];
int r[100010];
int dep[100010];
int ojciec[100010];
bool NIE_DA_SIE;
int root2 = -1;
int root[100010];

void dfs(int x){
	r[x] = 1;
	odw[x] = 1;
	low[x] = dep[x];
	int przeciwne = 0;
	vector<int>synowie;
	for(auto j: graf[x]){
		if(!odw[j]){
			synowie.push_back(j);
			dfs(j);
			if(root2!=-1)return;
			if(NIE_DA_SIE)return;
			r[x]+=r[j];
			low[x] = min(low[x], low[j]);
			if(low[j]<dep[x])
				przeciwne+=r[j];
		}
		else{
			low[x] = min(low[x], dep[j]);
		}
	}
	if(r[x]<a)return;
	if(r[x]-przeciwne<=n-a){//da sie
		for(auto j: synowie){
			if(r[x]<=n-a)break;
			ojciec[j] = ojciec[x];
			r[x]-=r[j];
		}
		ojciec[x] = -1;
		root2 = x;
		return;
	}
	if(r[x]-przeciwne>n-a){//nie da sie
		NIE_DA_SIE = 1;
		return;
	}
	
}

void dfs0(int x){
	odw[x] = 1;
	for(auto j: graf[x])
		if(!odw[j]){
			dep[j] = dep[x]+1;
			dfs0(j);
			ojciec[j] = x;
		}
	
}
void dfs2(int x){
	if(ojciec[x]==-1)
		root[x] = x;
	else
		root[x] = root[ojciec[x]];	
	odw[x] = 1;
	for(auto j: graf[x])
		if(!odw[j]){
			dfs2(j);
		}
	
}
vector<int>zbior[100010];

vector<int>split;
int rozmiar;
void dfs3(int x, int war){
	odw[x] = 1;
	if(war==0){
		if(rozmiar<a){
			split[x] = 0;
			rozmiar++;
		}
		else
			split[x] = 2;
	}
	else{
		if(rozmiar<b){
			split[x] = 1;
			rozmiar++;
		}
		else
			split[x] = 2;		
	}
	for(auto j: graf[x])
		if(!odw[j])
			dfs3(j, war);
	
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
	n = N, a = A, b = B, c = C;
	int m = p.size(), i;
	ojciec[0] = -1;
	pair<int,int> rozmiary[3] = {{a, 1},{b,2},{c, 3}};
	sort(rozmiary, rozmiary+3);
	a = rozmiary[0].first, b = rozmiary[1].first, c = rozmiary[2].first;
	for(i=0;i<m;i++){
		graf[p[i]].push_back(q[i]);
		graf[q[i]].push_back(p[i]);
	}
	dfs0(0);
	for(i=0;i<n;i++)odw[i] = 0;
	dfs(0);
	vector<int> res(n,0);
	if(NIE_DA_SIE)return res;
	for(i=0;i<n;i++)odw[i] = 0;
	dfs2(0);
	for(i=0;i<n;i++)zbior[root[i]].push_back(i);
	int root1 = 0;
	if(zbior[root1].size()<zbior[root2].size())swap(root1, root2);
	for(i=0;i<n;i++)graf[i].clear();
	for(i=0;i<m;i++)
		if(root[p[i]]==root[q[i]]){
			graf[p[i]].push_back(q[i]);
			graf[q[i]].push_back(p[i]);			
		}
	
	for(i=0;i<n;i++)odw[i] = 0;
	split.resize(n);
	rozmiar = 0;
	dfs3(root2, 0);//szukam a
	rozmiar = 0;
	dfs3(root1, 1);//szukam b
	for(i=0;i<n;i++)
		split[i] = rozmiary[split[i]].second;
	return split;
}

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