Submission #1225988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225988		Jer	Fun Tour (APIO20_fun)	C++20	10 / 100	2095 ms	328 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
#include <vector>

using namespace std;
const int MAXN = 505;
vector<int> con[MAXN];
bool used[MAXN];

pair<int, int> find_depth(int curr, int par){ // depth, node
	pair<int, int> res = {-1, -1};

	for (auto i : con[curr]){
		if (i == par or used[i]) continue;

		pair<int, int> b = find_depth(i, curr);
		if (b.first > res.first) res = b;
	}

	if (res.first == -1)
		return {1, curr};
	return {res.first + 1, res.second};
}

int find_remove(int start){ // node
	pair<int, int> best ={-1, -1};
	for (auto i : con[start]){
		if (used[i]) continue;

		pair<int, int> res = find_depth(i, start);
		if (best.second == -1 or (best.second != res.second and best.first < res.first))
			best = res;
	}

	return best.second;
}

void make_tree(int n){
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (hoursRequired(i, j) == 1)
				con[i].push_back(j), con[j].push_back(i);
}

std::vector<int> createFunTour(int n, int Q) {
  	vector<int> res;

	make_tree(n);

	int deep = find_depth(0, -1).second;
	int total = n;
	int prev = deep, t;

	while (total > 2){
		t = find_remove(prev);
		total--;
		used[t] = true;
		res.push_back(t);
		prev = t;
	}

	for (int i = 0; i < n; i++)
		if (!used[i]) res.push_back(i);

	return res;
}

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