Submission #1032306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032306		0npata	Fun Tour (APIO20_fun)	C++17	26 / 100	21 ms	504 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);
	}
}


std::vector<int> createFunTour(int N, int Q) {
	if(N>500) {
		vec<int> ans(0);
		for(int i = N-1; i>=0; i--) {
			ans.push_back(i);
		}
		return ans;
	}


	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)

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:66:21: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |  assert(used.size() == N);
      |         ~~~~~~~~~~~~^~~~

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