Submission #1067931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067931		pcc	Split the Attractions (IOI19_split)	C++17	0 / 100	573 ms	1048576 KiB

split

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

using namespace std;

const int mxn = 2e5+10;

vector<int> ans;
int N,A,B,C;
int sz[mxn];
vector<int> tree[mxn];
vector<int> perm;
vector<int> tar;

void dfs(int now,int par){
	sz[now] = 1;
	for(auto nxt:tree[now]){
		if(nxt == par)continue;
		dfs(nxt,now);
		sz[now] += sz[nxt];
	}
	return;
}
int find_centroid(int now,int par,int tar){
	for(auto nxt:tree[now]){
		if(nxt == par)continue;
		if(sz[nxt]>tar)return find_centroid(nxt,now,tar);
	}
	return now;
}

void color(int now,int par,int &cnt,int col){
	if(!cnt)return;
	cnt--;
	ans[now] = col;
	for(auto nxt:tree[now]){
		if(nxt == par)continue;
		color(nxt,now,cnt,col);
	}
	return;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	ans = vector<int>(n,0);
	N = n,A = a,B = b,C = c;
	tar = {A,B,C};
	perm = {0,1,2};
	sort(perm.begin(),perm.end(),[&](int a,int b){return tar[a]<tar[b];});
	sort(tar.begin(),tar.end());
	for(int i = 0;i<p.size();i++){
		int a = p[i],b = q[i];
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	dfs(0,0);
	int cen = find_centroid(0,0,sz[0]>>1);
	dfs(cen,cen);
	sort(tree[cen].begin(),tree[cen].end(),[](int a,int b){return sz[a]<sz[b];});
	ans[cen] = perm[1];
	tar[1]--;
	for(auto nxt:tree[cen]){
		color(nxt,cen,tar[1],perm[1]+1);
	}
	int big = tree[cen].back();
	if(sz[big]<tar[0])return vector<int>(N,0);
	color(big,cen,tar[0],perm[0]+1);
	for(auto &i:ans)if(!i)i = perm[2]+1;
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i = 0;i<p.size();i++){
      |                ~^~~~~~~~~

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