Submission #147654

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

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=100005;
vector<pii> V;
int warna[MAXN],subtree[MAXN],root1,root2,N,brp;
vector<int> adj[MAXN];
bool ada=false;

void dfs(int now,int par){
	subtree[now]=1;
	for(auto nxt : adj[now]){
		if(nxt==par)continue;
		dfs(nxt,now);
		subtree[now]+=subtree[nxt];
	}
}

void dfs2(int now,int par){
	for(auto nxt : adj[now]){
		if(nxt==par)continue;
		int kecil=min(subtree[nxt],N-subtree[nxt]),besar=N-kecil;
		if(kecil>=V[0].first && besar>=V[1].first){
			ada=true;
			if(kecil==subtree[nxt]){
				root1=nxt;
				root2=now;
			}
			else{
				root1=now;
				root2=nxt;
			}
			return;
		}
		dfs2(nxt,now);
	}
}

void dfs3(int now,int par,int id){
	if(brp==V[id].first)return;
	warna[now]=V[id].second;
	brp++;
	for(auto nxt : adj[now]){
		if(nxt==par)continue;
		dfs3(nxt,now,id);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N=n;
	V.push_back({a,1});V.push_back({b,2});V.push_back({c,3});
	sort(V.begin(),V.end());
	memset(warna,0,sizeof(warna));
	vector<int> res;
	for(int i=0;i<n;i++)res.push_back(0);
	for(int i=0;i<p.size();i++){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	dfs(0,-1);
	dfs2(0,-1);
	if(!ada)return res;
	brp=0;
	dfs3(root1,root2,0);
	brp=0;
	dfs3(root2,root1,1);
	res.clear();
	for(int i=0;i<n;i++){
		if(warna[i]==0)warna[i]=V[2].second;
		res.push_back(warna[i]);
	}
	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();i++){
              ~^~~~~~~~~

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