Submission #437567

#	Time	Username	Problem	Language	Result	Execution time	Memory
437567		Sohsoh84	Fun Tour (APIO20_fun)	C++14	26 / 100	143 ms	14840 KiB

fun

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

int n;
bool vis[MAXN];

int Req(int v, int u) {
	v--, u--;
	return hoursRequired(v, u);
}

int Sub(int v, int u) {
	v--, u--;
	return attractionsBehind(v, u);
}

int Diam(int v) {
	int ans = 0, ans_v = v;
	for (int i = 1; i <= n; i++) {
		if (vis[i]) continue;
		int d = Req(v, i);
		if (d > ans) {
			ans = d;
			ans_v = i;
		}
	}

	return ans_v;
}

std::vector<int> createFunTour(int N, int Q) {
	n = N;	
	vector<int> ans;

	int v = Diam(1);
	vis[v] = true;
	ans.push_back(v - 1);
	
	for (int i = 0; i < n - 1; i++) {
		int u = Diam(v);
		vis[u] = true;
		ans.push_back(u - 1);
		v = u;
	}
	
	return ans;
}

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