Submission #387168

#	Time	Username	Problem	Language	Result	Execution time	Memory
387168		milleniumEeee	Fun Tour (APIO20_fun)	C++17	26 / 100	116 ms	17260 KiB

fun

////////////////////////////////
#include "fun.h"
//#include "grader.cpp"
////////////////////////////////
#include <bits/stdc++.h>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define pii pair<int, int>
using namespace std;

const int MAXN = (int)1e5 + 5;
const int MAXQ = (int)4e5 + 5;

vector <int> g[MAXN];
bool used[MAXN];
int dist[MAXN];
int n;

void calc(int v, int par, int len) {
	dist[v] = len;
	for (int to : g[v]) {
		if (to == par) {
			continue;
		}
		calc(to, v, len + 1);
	}
}

int get_max() {
	int pos = -1, mx = 0;
	for (int i = 0; i < n; i++) {
		if (!used[i] && dist[i] > mx) {
			mx = dist[i];
			pos = i;
		}
	}
	return pos;
}

vector <int> createFunTour(int N, int Q) {
	n = N;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (hoursRequired(i, j) == 1) {
				g[i].pb(j);
				g[j].pb(i);
			}
		}
	}
	int a = 1;
	calc(a, -1, 0);
	int b = get_max();
	calc(b, -1, 0);
	int c = get_max();
	vector <int> ans = {b, c};
	used[b] = used[c] = 1;
	int used_cnt = 2;
	int last = c;
	while (used_cnt < n) {
		calc(last, -1, 0);
		int nxt = get_max();
		last = nxt;
		ans.pb(nxt);
		used[last] = 1;
		used_cnt++;
	}
	return ans;
}
/*
8 400000
5 3
1 3
4 3
6 5
2 5
5 0
7 3
*/

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