Submission #1247123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247123		countless	Towns (IOI15_towns)	C++20	0 / 100	11 ms	328 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) {
	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});
	};

	return max(work(fir, sec, cands[0].second), work(fir, sec, cands[1].second));
}

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