Submission #443311

#	Time	Username	Problem	Language	Result	Execution time	Memory
443311		vanic	Split the Attractions (IOI19_split)	C++14	22 / 100	97 ms	14064 KiB

split

#include "split.h"
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cassert>

using namespace std;

const int maxn=2e5+5;

int vel[3];
int ind[3];
vector < int > ms[maxn];
int n, m;

bool cmp(int a, int b){
	return vel[a]<vel[b];
}

int djeca[maxn];
int parent[maxn];

int dfs(int x, int prosl){
	djeca[x]=1;
	parent[x]=prosl;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			djeca[x]+=dfs(ms[x][i], x);
		}
	}
	return djeca[x];
}

int centroid(int x, int prosl){
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl && djeca[ms[x][i]]>n/2){
			return centroid(ms[x][i], x);
		}
	}
	return x;
}

vector < int > col;
int treba;
int koja, zamj;

void dfs1(int x, int prosl){
	if(treba){
		treba--;
		col[x]=koja;
	}
	else{
		col[x]=zamj;
	}
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			dfs1(ms[x][i], x);
		}
	}
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n=N;
	col.resize(n, 0);
	m=p.size();
	vel[0]=a;
	vel[1]=b;
	vel[2]=c;
	for(int i=0; i<3; i++){
		ind[i]=i;
	}
	sort(ind, ind+3, cmp);
	for(int i=0; i<m; i++){
		ms[p[i]].push_back(q[i]);
		ms[q[i]].push_back(p[i]);
	}
	if(m!=n-1){
		assert(0);
	}
	dfs(0, 0);
	int x=centroid(0, 0);
	dfs(x, x);
	int traz=vel[ind[0]];
	int pos, naj=1e9;
	for(int i=0; i<n; i++){
		if(djeca[i]>=traz){
			if(naj>djeca[i]){
				naj=djeca[i];
				pos=i;
			}
		}
	}
	
	if(n-naj<vel[ind[1]]){
		return col;
	}
	treba=traz;
	koja=ind[0]+1;
	zamj=ind[2]+1;
	dfs1(pos, parent[pos]);
	koja=ind[1]+1;
	treba=vel[ind[1]];
	dfs1(parent[pos], pos);
	return col;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:104:6: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |  dfs1(parent[pos], pos);
      |  ~~~~^~~~~~~~~~~~~~~~~~

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