Submission #1247613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247613		countless	Towns (IOI15_towns)	C++20	In queue	0 ms	0 KiB

towns

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

map<pair<int, int>, ll> memo;

ll query(int i, int j) {
	if (i == j) return 0;
	if (i > j) swap(i, j);
	if (memo.count({i, j})) return memo[{i, j}];

	return memo[{i, j}] = getDistance(i, j);
}

int hubDistance(int N, int sub) {
	memo.clear();
	ll best = LLONG_MAX;
	ll mn, fir = -1, sec = -1, mid = -1;

	mn = -1;
	for (int i = 0; i < N; i++) {
		ll curr = query(0, i);
		if (curr > mn) {
			mn = curr;
			fir = i;
		}
	}

	mn = -1;
	for (int i = 0; i < N; i++) {
		ll curr = query(fir, i);
		if (curr > mn) {
			mn = curr;
			sec = i;
		}
	}

	auto work = [&](ll a, ll b, ll c) -> ll {
		ll AB = query(a, b);
		ll BC = query(b, c);
		ll CA = query(c, a);
		cerr << AB sp BC sp CA << endl;
		ll ABC = (AB+BC+CA) / 2;
		ll A = ABC-BC, B = ABC-CA, C = ABC-AB;
		cerr << A sp B sp C << endl;
		return max({A, B, C});
	};

	ll oth = (fir == 0 or sec == 0 ? (fir == 1 or sec == 1 ? 2 : 1) : 0);
	ll ans = work(oth, fir, sec);
	// for (int i = 0; i < N; i++) {
	// 	ans = min(ans, work(fir, sec, i));
	// }

	return ans;
}