Submission #1215133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215133		Luvidi	Split the Attractions (IOI19_split)	C++20	40 / 100	64 ms	25160 KiB

split

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

const int maxn=1e5;
vector<int> ad[maxn],tr[maxn],cl;
int sz[maxn],s1,s2,n,cnt;
bool vs[maxn];
pair<int,int> pp;

void dfs(int v,int p){
	sz[v]=1;
	vs[v]=1;
	for(int u:ad[v])if(!vs[u]){
		tr[u].push_back(v);
		tr[v].push_back(u);
		dfs(u,v);
		sz[v]+=sz[u];
	}
	if(v!=p&&sz[v]>=s1&&n-sz[v]>=s2)pp={v,p};
}

void dfs2(int v,int p,int c){
	if(cnt>0)cl[v]=c;
	cnt--;
	for(int u:tr[v])if(u!=p)dfs2(u,v,c);
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n=N;
	for(int i=0;i<p.size();i++){
		ad[p[i]].push_back(q[i]);
		ad[q[i]].push_back(p[i]);
	}
	int ss[]={a,b,c};
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++)if(i!=j){
			s1=ss[i],s2=ss[j],pp={-1,-1};
			memset(vs,0,sizeof(vs));
			for(int x=0;x<n;x++)tr[x].clear();
			dfs(0,0);
			if(pp.first!=-1){
				cl=vector<int>(n,4-i-j);
				cnt=s1;
				dfs2(pp.first,pp.second,i+1);
				cnt=s2;
				dfs2(pp.second,pp.first,j+1);
				return cl;
			}
		}
	}
	return vector<int>(n,0);
}

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