Submission #1135453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135453		gyg	Towns (IOI15_towns)	C++20	25 / 100	9 ms	328 KiB

towns

// Note: 0-indexed, multiple tests

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 115, INF = 2e9;

int n;

arr<int, N> dst;
int fr(int u) {
	pii mx = {-1, -1};
	for (int v = 1; v <= n; v++)
		dst[v] = getDistance(u - 1, v - 1), mx = max(mx, {dst[v], v});
	assert(mx.sec != -1);
	return mx.sec;
}

arr<int, N> a_dst, b_dst;
set<int> df;
int hubDistance(int _n, int _s) {
	n = _n;

	int a = fr(1);
	int b = fr(a);
	a_dst = dst;
	fr(b);
	b_dst = dst;

	df.clear();
	for (int u = 1; u <= n; u++)
		if (u != a && u != b) df.insert(a_dst[u] - b_dst[u]);

	// cout << a << " " << b << " " << a_dst[b] << endl;
	
	int ans = INF;
	for (int x : df) {
		int in_a = (x + a_dst[b]) / 2;
		int in_b = (-x + a_dst[b]) / 2;
		ans = min(ans, max(in_a, in_b));
	}
	return ans;
}

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39