제출 #1131488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131488		boris_mihov	Fun Tour (APIO20_fun)	C++17	26 / 100	73 ms	15944 KiB

fun

#include "fun.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n, q;
bool active[MAXN];
std::vector <int> g[MAXN];

std::pair <int,int> find_furthest(int node, int par)
{
	std::pair <int,int> ans = {0, -INF};
	if (active[node])
	{
		ans = {node, 0};
	}

	for (const int u : g[node])
	{
		if (u == par)
		{
			continue;
		}

		auto [v, d] = find_furthest(u, node);
		if (d >= ans.second)
		{
			ans = {v, d + 1};
		}
	}

	return ans;
}

std::vector <int> createFunTour(int N, int Q)
{
	n = N; q = Q;
	for (int i = 1 ; i <= n ; ++i)
	{
		active[i] = true;
	}

	for (int i = 1 ; i <= n ; ++i)
	{
		for (int j = i + 1 ; j <= n ; ++j)
		{
			if (hoursRequired(i - 1, j - 1) == 1)
			{
				g[i].push_back(j);
				g[j].push_back(i);
			}
		}
	}

	std::vector <int> sol;
	int root = find_furthest(1, 0).first;
	for (int i = 1 ; i <= n ; ++i)
	{
		active[root] = false;
		sol.push_back(root - 1);
		root = find_furthest(root, 0).first;
	}

	return sol;
}

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