Submission #290754

#	Time	Username	Problem	Language	Result	Execution time	Memory
290754		TadijaSebez	Fun Tour (APIO20_fun)	C++11	0 / 100	1 ms	384 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>

int SUB(int root,int x){return attractionsBehind(root,x);}
int DEP(int root,int x){return hoursRequired(root,x);}

const int N=100050;
int dep[N],sz[N];
int FindCentroid(int n){
	pii mx={0,0};
	for(int i=1;i<n;i++){
		sz[i]=SUB(0,i);
		dep[i]=DEP(0,i);
		if(sz[i]*2>=n)mx=max(mx,{dep[i],i});
	}
	return mx.second;
}
int type[N],dist[N];
vector<int> createFunTour(int n,int q){
	int cen=FindCentroid(n);
	vector<int> f;
	for(int i=0;i<n;i++){
		dist[i]=DEP(cen,i);
		if(dist[i]==1&&dep[i]==dep[cen]+1){
			f.pb(i);
			type[i]=f.size();
		}
	}
	type[cen]=-1;
	for(int j=0;j<f.size();j++){
		for(int i=0;i<n;i++)if(!type[i]){
			if(SUB(i,f[j])==n-sz[f[j]]+1)type[i]=j+1;
		}
	}
	for(int i=0;i<n;i++)if(!type[i])type[i]=3;
	priority_queue<pii> pq[3];
	for(int i=0;i<n;i++)if(type[i]>0)pq[type[i]-1].push({dist[i],i});
	vector<int> ans;
	int ban=-1;
	while(1){
		int mx=0,sz=0,o=-1;
		for(int i=0;i<3;i++)if(i!=ban){
			if(pq[i].size()){
				int now=pq[i].top().first;
				if(now>mx||(now==mx&&sz<pq[i].size()))mx=now,sz=pq[i].size(),o=i;
			}
		}
		if(o==-1)break;
		ban=o;
		ans.pb(pq[o].top().second);
		pq[o].pop();
	}
	ans.pb(cen);
	return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int j=0;j<f.size();j++){
      |              ~^~~~~~~~~
fun.cpp:48:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     if(now>mx||(now==mx&&sz<pq[i].size()))mx=now,sz=pq[i].size(),o=i;
      |                          ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34