Submission #1032344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032344		0npata	Fun Tour (APIO20_fun)	C++17	26 / 100	26 ms	608 KiB

fun

#include "fun.h"

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

#define vec vector

const int MXN = 505;

vec<int> tree[MXN];
int depth[MXN];

void dfs1(int u, int p = -1) {
	for(int v : tree[u]) {
		if(v == p) continue;
		depth[v] = depth[u]+1;
		dfs1(v, u);
	}
}

void binaryTree(int N, int u, set<int>& used, vec<int>& ans) {
	int r = u*2+1;
	int l = u*2;
	vec<int> right(0);
	vec<int> left(0);

	vec<int> nw{l};
	while(nw.size() > 0) {
		int cur = nw.back();
		nw.pop_back();
		if(used.count(cur) || cur > N) continue;
		left.push_back(cur);
		nw.push_back(cur*2);
		nw.push_back(cur*2+1);
	}
	sort(left.begin(), left.end());
	nw = {r};
	while(nw.size() > 0) {
		int cur = nw.back();
		nw.pop_back();
		if(used.count(cur) || cur > N) continue;
		right.push_back(cur);
		nw.push_back(cur*2);
		nw.push_back(cur*2+1);
	}
	sort(right.begin(), right.end());

	for(int i = 0; i<min(left.size(), right.size()); i++) {
		ans.push_back(right[i]);
		ans.push_back(left[i]);
		used.insert(left[i]);
		used.insert(right[i]);
	}

	ans.push_back(u);
	if(left.size() > 0) {
		binaryTree(N, u*2, used, ans);
	}
}

std::vector<int> createFunTour(int N, int Q) {
	if(N>500) {
		vec<int> res(0);
		set<int> used{};
		binaryTree(N, 1, used, res);
		for(int i = 0; i<N; i++) res[i]--;
		return res;
	}


	for(int i = 0; i<N; i++) {
		for(int j = 0; j<N; j++) {
			if(i == j) {
				continue;
			}
			if(hoursRequired(i, j) == 1) {
				tree[i].push_back(j);
			}
		}
	}
	set<int> used;
	auto comp_depth = [&](int u) {
		depth[u] = 0;
		dfs1(u);
	};

	comp_depth(0);

	int x = 0;
	for(int i = 0; i<N; i++) {
		if(depth[i] > depth[x]) x = i;
	}

	vec<int> ans(0);

	for(int i = 0; i<N; i++) {
		comp_depth(x);
		for(int i = 0; i<N; i++) {
			if(!used.count(i) && depth[i] > depth[x]) x = i;
		}

		ans.push_back(x);
		used.insert(x);
	}
	assert(used.size() == N);

	return ans;
}

Compilation message (stderr)

fun.cpp: In function 'void binaryTree(int, int, std::set<int>&, std::vector<int>&)':
fun.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   48 |  for(int i = 0; i<min(left.size(), right.size()); i++) {
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from fun.cpp:3:
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:105:21: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |  assert(used.size() == N);
      |         ~~~~~~~~~~~~^~~~

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