Submission #965985

#	Time	Username	Problem	Language	Result	Execution time	Memory
965985		Gromp15	Fun Tour (APIO20_fun)	C++17	26 / 100	77 ms	15944 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define db double
#define ll long long
#define ar array
template<typename T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

std::vector<int> createFunTour(int N, int Q) {
	vector<vector<int>> adj(N);
	for (int i = 0; i < N; i++) {
		for (int j = i+1; j < N; j++) {
			if (hoursRequired(i, j) == 1) {
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}
	vector<bool> vis(N);
	auto get = [&](int x) {
		queue<int> q;
		vector<int> dist(N, 1e9);
		dist[x] = 0;
		q.push(x);
		int f = -1, d = -1;
		while (q.size()) {
			int v = q.front(); q.pop();
			if (ckmax(d, dist[v])) f = v;
			for (int u : adj[v]) if (!vis[u]) {
				if (ckmin(dist[u], dist[v] + 1)) {
					q.push(u);
				}
			}
		}
		return f;
	};
	vector<int> ans(N);
	for (int i = 0, j = 0; i < N; i++) {
		j = get(j);
		ans[i] = j, vis[j] = 1;
	}
	return ans;
}

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