Submission #420077

#	Time	Username	Problem	Language	Result	Execution time	Memory
420077		maximath_1	Fun Tour (APIO20_fun)	C++11	100 / 100	309 ms	21408 KiB

fun

#include "fun.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int> dist, adj, ans;
vector<pair<int, int> > child[4];

vector<int> createFunTour(int n, int q){
	adj.clear(); dist.clear(); ans.clear();
	for(int i = 0; i < 4; i ++) child[i].clear();

	int rt = 0, cent = 0, mx_sz = n + 5;	
	for(int i = 1; i < n; i ++){
		int w = attractionsBehind(rt, i);
		if(w >= (n + 1) / 2 && w < mx_sz){
			cent = i; mx_sz = w;
		}
	}

	rt = cent;
	dist.resize(n);
	for(int i = 0; i < n; i ++){
		if(i == rt) dist[i] = 0;
		else dist[i] = hoursRequired(i, rt);
		if(dist[i] == 1) adj.push_back(i);
	}

	for(int i = 0; i < n; i ++) if(i != rt){
		bool ok = 0;
		for(int j = 1; j < adj.size(); j ++)
			if(dist[i] == hoursRequired(adj[j], i) + 1){
				child[j].push_back({dist[i], i});
				ok = 1; break;
			}
		if(!ok)
			child[0].push_back({dist[i], i});
	}

	int mn = 0;
	for(int i = 1; i < 3; i ++)
		if(child[i].size() < child[mn].size())
			mn = i;
	child[mn].push_back({dist[rt], rt});

	for(int i = 0; i < adj.size(); i ++)
		sort(child[i].begin(), child[i].end());

	int last = -1, cnt = n;
	for(; cnt > 0;){
		if(max(child[0].size(), max(child[1].size(), child[2].size())) * 2 == cnt)
			break;

		int nw = -1;
		for(int i = 0; i < 3; i ++) if(i != last && child[i].size()){
			if(nw == -1 || child[nw].back().first < child[i].back().first)
				nw = i;
		}

		ans.push_back(child[nw].back().second);
		child[nw].pop_back(); last = nw;
		cnt --;
	}

	if(child[0].size() < child[1].size()){
		swap(child[0], child[1]);
		if(last == 0) last = 1;
		else if(last == 1) last = 0;
	}
	if(child[0].size() < child[2].size()){
		swap(child[0], child[2]);
		if(last == 0) last = 2;
		else if(last == 2) last = 0;
	}
	if(child[1].size() < child[2].size()){
		swap(child[1], child[2]);
		if(last == 1) last = 2;
		else if(last == 2) last = 1;
	}

	if(child[2].size() && child[2].back().first > child[1].back().first){
		swap(child[1], child[2]);
		if(last == 1) last = 2;
		else if(last == 2) last = 1;
	}

	if(child[1].size() && (last == 0 || (last == 2 && child[1].back().first > child[0].back().first))){
		ans.push_back(child[1].back().second);
		child[1].pop_back(); cnt --;
		last = 1;
	}

	while(cnt){
		if(child[0].size()){
			ans.push_back(child[0].back().second);
			child[0].pop_back(); cnt --;
		}

		if(child[1].empty() && child[2].empty()) continue;

		if(child[1].empty()){
			ans.push_back(child[2].back().second);
			child[2].pop_back(); cnt --;
			continue;
		}

		if(child[2].empty()){
			ans.push_back(child[1].back().second);
			child[1].pop_back(); cnt --;
			continue;
		}

		if(child[1].back().first < child[2].back().first)
			swap(child[1], child[2]);
		ans.push_back(child[1].back().second);
		child[1].pop_back(); cnt --;
	}

	return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int j = 1; j < adj.size(); j ++)
      |                  ~~^~~~~~~~~~~~
fun.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i = 0; i < adj.size(); i ++)
      |                 ~~^~~~~~~~~~~~
fun.cpp:52:70: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   52 |   if(max(child[0].size(), max(child[1].size(), child[2].size())) * 2 == cnt)
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~

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