Submission #827515

#	Time	Username	Problem	Language	Result	Execution time	Memory
827515		Baytoro	Split the Attractions (IOI19_split)	C++17	40 / 100	70 ms	19040 KiB

split

#include "split.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
const int maxN=1e5+5;
vector<int> ans(maxN),g[maxN];
int used[maxN];
vector<pair<int,int>> e;
int n;
void dfs(int x){
	used[x]=1;
	for(auto it: g[x]){
		if(!used[it]){
			dfs(it);
			e.push_back({x,it});
		}
	}
}
int sz[maxN];
int u=-1,v=-1,a,b,c;
void dfs1(int x, int p){
	sz[x]=1;
	for(auto it: g[x]){
		if(it==p) continue;
		dfs1(it,x);
		sz[x]+=sz[it];
	}
	if(min(sz[x],n-sz[x])>=a){
		u=x,v=p;
	}
}
int dfs2(int x, int p, int c, int v){
	if(v==0) return 0;
	ans[x]=c;v--;
	
	for(auto it: g[x]){
		if(it==p) continue;
		v=dfs2(it,x,c,v);
	}
	return v;
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
	int A=1,B=2,C=3,m=p.size();
	a=_a,b=_b,c=_c;
	n=_n;
	if(a>b){
		swap(a,b);
		swap(A,B);
	}
	if(b>c){
		swap(b,c);
		swap(B,C);
	}
	if(a>b){
		swap(a,b);
		swap(A,B);
	}
	for(int i=0;i<m;i++){
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	dfs(0);
	for(int i=0;i<n;i++){
		g[i].clear();
	}
	for(auto c: e){
		g[c.fr].push_back(c.sc);
		g[c.sc].push_back(c.fr);
	}
	dfs1(0,0);
	vector<int> res(n,0);
	if(v==-1) return res;
	res=vector<int> (n,C);
	if(sz[u]>=b) swap(u,v);
	dfs2(u,v,A,a);
	dfs2(v,u,B,b);
	for(int i=0;i<n;i++)
		if(ans[i]) res[i]=ans[i];
	return res;
}

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