Submission #1227573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227573		faruk	Towns (IOI15_towns)	C++20	25 / 100	10 ms	328 KiB

towns

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

using namespace std;

typedef pair<int, int> pii;

map<pii, int > memo;
int my_query(int f, int t) {
	if (f > t)
		swap(f, t);
	if (memo.count(pii(f, t)))
		return memo[pii(f, t)];
	return memo[pii(f, t)] = getDistance(f, t);
}

int hubDistance(int N, int sub) {
	memo.clear();
	int f1 = 0; int best_dist = -1;
	for (int i = 1; i < N; i++)
		if (my_query(0, i) > best_dist)
			best_dist = my_query(0, i), f1 = i;
	int f2 = 0;
	for (int i = 1; i < N; i++)
		if (i != f1 and my_query(f1, i) > best_dist)
			f2 = i, best_dist = my_query(f1, i);

	// try all intermediates
	int R = 1e9;
	for (int d = 0; d < N; d++) {
		if (d == f1 || d == f2)
			continue;
		int x = best_dist;
		int y = my_query(f1, d);
		int z = my_query(f2, d);

		int d1 = (x + y - z) / 2;
		int d2 = x - d1;
		R = min(R, max(d1, d2));
	}

	return R;
}

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