Submission #1247125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247125		countless	Towns (IOI15_towns)	C++20	25 / 100	42 ms	480 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;
		}
	}

	// ll dia = mn;

	// vector<pair<ll, ll>> cands;
	// for (int i = 0; i < N; i++) {
	// 	ll curr = (query(fir, i) + query(sec, i) - query(fir, sec)) / 2;
	// 	ll cand = abs(curr - query(fir, sec));
	// 	cands.emplace_back(cand, i);
	// }
	// sort(cands.begin(), cands.end());

	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 ans = LLONG_MAX;
	for (int i = 0; i < N; i++) {
		ans = min(ans, work(fir, sec, i));
	}

	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