Submission #1031381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031381		Maite_Morale	Split the Attractions (IOI19_split)	C++14	0 / 100	468 ms	1048576 KiB

split

#include <bits/stdc++.h>
#include <cstdio>
#include <cassert>
using namespace std;
typedef long long ll;
#define MAX 500005
#define vll vector<ll>
#define pll pair<ll,ll>
#define S second
#define F first


vll v[MAX];
vector<int> rasta={};
ll band=0,subt=1,n,p[MAX],h[MAX],mx[3][MAX],a,b,c,tot;
ll dfs(ll x,ll y){
	// cerr<<"\n"<<x<<" "<<y<<"\n";
	h[x]=1;p[x]=y;
	for(auto w : v[x]){
		if(w!=y){
			h[x]+=dfs(w,x);
			mx[x][0]=h[w];
			sort(mx[x],mx[x]+3);
		}
	}
	if(h[x]<h[subt] && h[x]>=a)subt=x;
return h[x];
}
void dfs1(ll x,ll y,ll z){
	if(tot>0){
		rasta[x]=z;tot--;
		for(auto w : v[x]){
			if(w!=y){
				dfs1(w,x,z);
			}
		}
	}
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
	//rasta={0};
	rasta.assign(_n,0);
	pll ide[3]={{_a,1},{_b,2},{_c,3}};
	sort(ide,ide+3);
	n=_n;a=ide[0].F;b=ide[1].F;c=ide[2].F;
	for(int i=0;i<p.size();i++){
		v[p[i]].push_back(q[i]);
		v[q[i]].push_back(p[i]);
	}
	dfs(0,0);
	if(mx[0][p[subt]]>a || (mx[0][p[subt]]==a && mx[1][p[subt]]>=a)){
		rasta.assign(n,(int)ide[2].S);
		if(h[subt]>n-h[subt]){
			tot=b;
			dfs1(subt,p[subt],ide[1].S);
			tot=a;
			dfs1(p[subt],subt,ide[0].S);
	
		}
		else{
			tot=a;
			dfs1(subt,p[subt],ide[0].S);
			tot=b;
			dfs1(p[subt],subt,ide[1].S);
		}
	} 
return rasta;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  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