Submission #464043

#	Time	Username	Problem	Language	Result	Execution time	Memory
464043		Elias	Fun Tour (APIO20_fun)	C++17	0 / 100	2098 ms	19108 KiB

fun

#include "fun.h"

#include <vector>
#include <climits>

using namespace std;

vector<vector<int>> adj;
vector<bool> blocked;

pair<int, int> dfsLongest(int i, int parent = -1)
{
	pair<int, int> longest{0, i};

	for (int c : adj[i])
	{
		if (c == parent || blocked[c])
			continue;

		auto newLongest = dfsLongest(c, i);
		newLongest.first++;

		longest = max(longest, newLongest);
	}

	return longest;
}

vector<signed> createFunTour(signed N, signed Q)
{

	adj = vector<vector<int>>(N);
	for (int i = 1; i < N; i++)
	{
		int parent = (i - 1) / 2;
		adj[parent].push_back(i);
		adj[i].push_back(parent);
	}

	vector<int> solution;
	blocked = vector<bool>(N);

	int node = dfsLongest(0).second;

	for (int i = 0; i < N; i++)
	{
		int longestNode = dfsLongest(node).second;
		solution.push_back(node);
		blocked[node] = true;
		node = longestNode;
	}
	return solution;
}

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