Submission #434793

#	Time	Username	Problem	Language	Result	Execution time	Memory
434793		dqhungdl	Fun Tour (APIO20_fun)	C++17	66 / 100	332 ms	39136 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;

bool cmp(vector<ii> g1,vector<ii> g2) {
	return g1.size()>g2.size();
}

vector<ii> merge(vector<ii> g1,vector<ii> g2) {
	while(g2.size()>0) {
		g1.push_back(g2.back());
		g2.pop_back();
	}
	sort(g1.begin(),g1.end());
	return g1;
}

int getBack(vector<ii> &V) {
	if(V.size()==0)
		return -1;
	return V.back().first;
}

std::vector<int> createFunTour(int N, int Q) {
	// Special case
	if(N==2)
		return {0,1};
	// Find centroid
	int R=0,minVal=1e9;
	for(int i=1;i<N;i++) {
		int subtree=attractionsBehind(R,i);
		if(subtree>=(N+1)/2&&minVal>subtree) {
			minVal=subtree;
			R=i;
		}
	}
	// Find distance and adjacents from centroid R
	vector<int> adj,dist(N);
	for(int i=0;i<N;i++) {
		dist[i]=hoursRequired(R,i);
		if(dist[i]==1)
			adj.push_back(i);
	}
	// Divide into parts
	vector<ii> g[adj.size()];
	for(int i=0;i<N;i++) {
		if(i==R)
			continue;
		bool valid=false;
		for(int j=0;j<adj.size();j++)
			if(adj[j]==i) {
				g[j].push_back({1,i});
				valid=true;
				break;
			}
		if(valid)
			continue;
		for(int j=0;j<adj.size()-1;j++)
			if(dist[i]==hoursRequired(i,adj[j])+1) {
				g[j].push_back({dist[i],i});
				valid=true;
				break;
			}
		if(!valid)
			g[adj.size()-1].push_back({dist[i],i});
	}
	// Sort sets
	sort(g,g+adj.size(),cmp);
	for(int i=0;i<adj.size();i++)
		sort(g[i].begin(),g[i].end());
	// Generate path
	vector<int> rs;
	int turn=0;
	if(adj.size()==3) {
		int pre=-1;
		while(g[0].size()>0||g[1].size()>0||g[2].size()>0) {
			if(g[0].size()+g[1].size()==g[2].size()) {
				g[0]=merge(g[0],g[1]);
				g[1]=g[2];
				turn=(pre==0||pre==1?1:0);
				break;
			} else if(g[0].size()+g[2].size()==g[1].size()) {
				g[0]=merge(g[0],g[2]);
				turn=(pre==0||pre==2?1:0);
				break;
			} else if(g[1].size()+g[2].size()==g[0].size()) {
				g[1]=merge(g[1],g[2]);
				turn=(pre==0?1:0);
				break;
			}
			int newPre=-1;
			for(int i=0;i<adj.size();i++) {
				if(i==pre||g[i].size()==0)
					continue;
				if(newPre==-1||g[newPre].back()<g[i].back())
					newPre=i;
			}
			assert(pre!=newPre);
			pre=newPre;
			rs.push_back(g[pre].back().second);
			g[pre].pop_back();
		}
		if(g[turn^1].size()>0&&g[turn^1].back().first>g[turn].back().first
			&&rs.size()>0&&hoursRequired(rs.back(),g[turn^1].back().second)==dist[rs.back()]+dist[g[turn^1].back().second])
			turn^=1;
	}
	while(g[0].size()>0||g[1].size()>0) {
		if(g[turn].size()==0)
			turn^=1;
		rs.push_back(g[turn].back().second);
		g[turn].pop_back();
		turn^=1;
	}
	rs.push_back(R);
	//for(int u:rs)
	//	cerr<<u<<' ';
	return rs;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int j=0;j<adj.size();j++)
      |               ~^~~~~~~~~~~
fun.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int j=0;j<adj.size()-1;j++)
      |               ~^~~~~~~~~~~~~
fun.cpp:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i=0;i<adj.size();i++)
      |              ~^~~~~~~~~~~
fun.cpp:95:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    for(int i=0;i<adj.size();i++) {
      |                ~^~~~~~~~~~~

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