Submission #397374

#	Time	Username	Problem	Language	Result	Execution time	Memory
397374		Kevin_Zhang_TW	Fun Tour (APIO20_fun)	C++17	47 / 100	146 ms	15472 KiB

fun

#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
 
const int MAX_N = 100010, MAX_D = 17;
 
int qdis(int a, int b) { return hoursRequired(a, b); }
int sbsz(int rt, int x) { return attractionsBehind(rt, x); }
 
// always go to the farthest point possible
// but it doesn't rely on deg(x) <= 3
 
std::vector<int> createFunTour(int N, int Q) {
	int cen = -1, sz = N + 10;
	for (int i = 0;i < N;++i) {
		int q = sbsz(0, i);
		if (q * 2 <= N) continue;
		if (chmin(sz, q))
			cen = i;
	}
	if (N == 2) return {0, 1};

	vector<int> dis(N);
	vector<int> nei;
	for (int i = 0;i < N;++i) {
		dis[i] = qdis(cen, i);
		if (dis[i] == 1)
			nei.pb(i);
	}
	vector<vector<pair<int,int>>> tree(nei.size());

	for (int i = 0;i < N;++i) if (i != cen) {
		for (int j = 0;j < nei.size();++j) {
			if (j+1 == nei.size() || dis[i] == 1 + qdis(nei[j], i)) {
				tree[j].pb(dis[i], i);
				break;
			}
		}
	}

	for (auto &vec : tree) sort(AI(vec));

	sort(AI(tree), [&](auto &a, auto &b) { 
			return a.size() < b.size();
	});

	vector<int> res;

	int ts = N-1;

	if (tree.size() == 3) {
		int ind = -1;
		for (int j = 0;j < 3;++j)
			if (tree[j].size() * 2 >= ts) {
				ind = j;
			}
		if (ind != -1) {
			assert(ind > 0);
			int os = tree[0].size();
			tree[0].insert(end(tree[0]), AI(tree[3 - ind]));
			inplace_merge(begin(tree[0]), begin(tree[0]) + os, end(tree[0]));
			tree.erase(begin(tree) + 3 - ind);
		}
	}

	sort(AI(tree), [&](auto &a, auto &b) {
		return a.back() < b.back();
	});



	for (int t = 1;t < N;++t, --ts) {
		if (tree.size() == 3) {
			int ind = -1;
			for (int j = 0;j < 3;++j)
				if (tree[j].size() * 2 >= ts) {
					ind = j;
					break;
				}
			if (ind != -1) {
				assert(ind > 0);
				int os = tree[0].size();
				tree[0].insert(end(tree[0]), AI(tree[3 - ind]));
				inplace_merge(begin(tree[0]), begin(tree[0]) + os, end(tree[0]));
				tree.erase(begin(tree) + 3 - ind);

				assert(tree.size() == 2);

				assert(abs((int)tree[0].size() - (int)tree[1].size()) <= 1);
			}
		}
		


		if (tree.size() == 3 && tree[2].back() > tree[1].back())
			swap(tree[1], tree[2]);

		if (tree[1].empty()) {
			swap(tree[0], tree[1]);
			assert(tree.size() == 2);
		}

		res.pb(tree[1].back().second);
		tree[1].pop_back();

		swap(tree[0], tree[1]);

	}

	res.pb(cen);
	return res;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int j = 0;j < nei.size();++j) {
      |                  ~~^~~~~~~~~~~~
fun.cpp:48:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    if (j+1 == nei.size() || dis[i] == 1 + qdis(nei[j], i)) {
      |        ~~~~^~~~~~~~~~~~~
fun.cpp:68:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |    if (tree[j].size() * 2 >= ts) {
      |        ~~~~~~~~~~~~~~~~~~~^~~~~
fun.cpp:90:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |     if (tree[j].size() * 2 >= ts) {
      |         ~~~~~~~~~~~~~~~~~~~^~~~~

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