Submission #724911

#	Time	Username	Problem	Language	Result	Execution time	Memory
724911		hollwo_pelw	Fun Tour (APIO20_fun)	C++17	10 / 100	1 ms	340 KiB

fun

#include "fun.h"
// #include "grader.cpp"

#include <bits/stdc++.h>
using namespace std;

// int H = hoursRequired(0, N - 1);
// int A = attractionsBehind(0, N - 1);

vector<int> createFunTour(int N, int Q) {
	int centroid = 0, subsiz = N;
	for (int i = 1; i < N; i++) {
		int csubsiz = attractionsBehind(0, i);
		if (csubsiz > N / 2 && csubsiz < subsiz)
			centroid = i, subsiz = csubsiz;
	}

	vector<int> depth(N);
	for (int i = 0; i < N; i++)
		depth[i] = i == centroid ? 0 : hoursRequired(centroid, i);

	vector<int> g, type(N, 0);
	for (int i = 0; i < N; i++)
		if (depth[i] == 1) {
			g.push_back(i);
		}

	const int M = g.size();
	
	for (int i = 0; i < N; i++) if (i != centroid) {
		for (int j = 1; j < M; j++) {
			if (hoursRequired(g[j], i) == depth[i] - 1) {
				type[i] = j; break;
			}
		}
	}


	// cout << centroid << '\n';
	// cout << M << '\n';

	// for (int i = 0; i < N; i++) {
	// 	cout << depth[i] << ' ' << type[i] << '\n';
	// }

	vector<int> res;
	vector<pair<int, int>> group[M];
	for (int i = 0; i < N; i++) if (i != centroid)
		group[type[i]].emplace_back(depth[i], i);

	for (int i = 0; i < M; i++)
		sort(group[i].begin(), group[i].end());

	for (int turn = N - 1, f = -1; turn --; ) {
		int p = -1, c = -1;
		for (int i = 0; i < M; i++) {
			if (i != f && (int) group[i].size() > c)
				p = i, c = group[i].size();
		}
		assert(c > 0);
		res.push_back(group[p].back().second);
		group[p].pop_back(), f = p;
	}

	res.push_back(centroid);

	return res;
}

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