Submission #292078

#	Time	Username	Problem	Language	Result	Execution time	Memory
292078		cfalas	Split the Attractions (IOI19_split)	C++14	22 / 100	948 ms	1048580 KiB

split

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

using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORi(i,b,n) for(int i=b;i<n;i++)
#define FOA(i,n) for(auto i : n)
#define len(a) ((int)a.size())

vector<vi> adj;
int ssub[1000000];

vi ans;
vi par;
int A_VAL=1;
int B_VAL=2;
int C_VAL=3;
int dfs(int s, int p=-1){
	par[s] = p;
	ssub[s] = 1;
	for(auto v : adj[s]) if(v!=p) ssub[s]+=dfs(v, s);
	return ssub[s];
}

int acnt=0;
int A;
void traveA(int s, int p=-1){
	cerr<<s<<" "<<p<<endl;
	ans[s] = A_VAL;
	acnt++;
	for(auto v : adj[s]) if(v!=p) traveA(v, s);
	if(acnt>A) acnt--, ans[s] = C_VAL;
}

int bcnt=0;
int B;
void traveB(int s, int p=-1){
	//cout<<s<<" "<<p<<endl;
	//cout<<ans[s]<<endl;
	if(!ans[s]){
		ans[s] = B_VAL;
		bcnt++;
	}
	for(auto v : adj[s]) if(v!=p) traveB(v, s);
	if(bcnt>B && ans[s]==B_VAL) bcnt--, ans[s] = C_VAL;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	A = a;
	B = b;
	adj.assign(n+1, vi());
	ans.resize(n);
	par.resize(n+1);
	FOR(i,len(p)){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	dfs(1);

	int mindiffpos=0, mindiff=1000000000;
	FOR(i,n){
		if(ssub[i+1]>=a && ssub[i+1]<mindiff) mindiff = ssub[i+1], mindiffpos = i+1;
	}
	//cerr<<mindiff<<" "<<mindiffpos<<endl;
	int mindiffb=100000000, mindiffposb=0;
	FOR(i,n){
		if(ssub[i+1]>=b && ssub[i+1]<mindiffb) mindiffb = ssub[i+1], mindiffposb = i+1;
	}
	if(mindiff-a>mindiffb-b){
		swap(a,b);
		swap(A,B);
		swap(A_VAL, B_VAL);
		swap(mindiff,mindiffb);
		swap(mindiffpos,mindiffposb);
	}

	//cerr<<mindiff<<" "<<mindiffpos<<endl;
	int mindiffc=100000000, mindiffposc=0;
	FOR(i,n){
		if(ssub[i+1]>=c && ssub[i+1]<mindiffc) mindiffc = ssub[i+1], mindiffposc = i+1;
	}
	if(mindiff-a>mindiffc-c){
		swap(a,c);
		swap(A_VAL, C_VAL);
		swap(mindiff,mindiffc);
		swap(mindiffpos,mindiffposc);
	}
	cerr<<mindiff<<" "<<mindiffpos<<endl;
	cerr<<par[mindiffpos]<<endl;
	traveA(mindiffpos, par[mindiffpos]);
	traveB(1);
	FOR(i,n){
		if(ans[i]==B_VAL) b--;
		else if(ans[i]==A_VAL) a--;
		else ans[i]=C_VAL,c--;
		//cout<<ans[i]<<" ";
	}
	//cout<<endl;
	//cout<<a<<" "<<b<<" "<<c<<endl;
	if(a || b || c){
		ans.assign(n, 0);
	}
	return ans;


}

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