Submission #397396

#	Time	Username	Problem	Language	Result	Execution time	Memory
397396		Kevin_Zhang_TW	Fun Tour (APIO20_fun)	C++17	100 / 100	278 ms	21436 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) {
			assert(tree[j].size() * 2 <= N);
			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();
	});


	int ld = N * 2;

	int ls = N;

	int os = tree.size();

	const int inf = 1e9;

	pair<int,int> lst;

	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) {
					assert(tree[j].size() * 2 == ts);
					ind = j;
					break;
				}

			if (ind != -1) {
				assert(ind > 0);

				bool tg = lst < tree[3 - ind].back();

				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[0].size() == tree[1].size());

				if (tg) swap(tree[0], tree[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]);
		}

		lst = tree[1].back();

		auto [d, x] = tree[1].back(); tree[1].pop_back();

		res.pb(x);

		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)) {
      |        ~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from fun.cpp:1:
fun.cpp:68:30: 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 |    assert(tree[j].size() * 2 <= N);
      |           ~~~~~~~~~~~~~~~~~~~^~~~
fun.cpp:69: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]
   69 |    if (tree[j].size() * 2 >= ts) {
      |        ~~~~~~~~~~~~~~~~~~~^~~~~
fun.cpp:102: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]
  102 |     if (tree[j].size() * 2 >= ts) {
      |         ~~~~~~~~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from fun.cpp:1:
fun.cpp:103:32: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |      assert(tree[j].size() * 2 == ts);
      |             ~~~~~~~~~~~~~~~~~~~^~~~~
fun.cpp:87:6: warning: unused variable 'ld' [-Wunused-variable]
   87 |  int ld = N * 2;
      |      ^~
fun.cpp:89:6: warning: unused variable 'ls' [-Wunused-variable]
   89 |  int ls = N;
      |      ^~
fun.cpp:91:6: warning: unused variable 'os' [-Wunused-variable]
   91 |  int os = tree.size();
      |      ^~
fun.cpp:93:12: warning: unused variable 'inf' [-Wunused-variable]
   93 |  const int inf = 1e9;
      |            ^~~

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