Submission #1247119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247119		countless	Towns (IOI15_towns)	C++20	0 / 100	10 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;

	mn = LLONG_MAX;
	for (int i = 0; i < N; i++) {
		ll curr = (query(fir, i) + query(sec, i) - query(fir, sec)) / 2;
		ll cand = abs(curr - 2LL * query(fir, sec));
		if (cand < mn) {
			mn = cand;
			mid = i;
		}
	}

	ll AB = query(fir, sec);
	ll BC = query(sec, mid);
	ll CA = query(mid, fir);
	ll ABC = (AB+BC+CA) / 2;
	ll A = ABC-BC, B = ABC-CA, C = ABC-AB;
	return max({A, B, C});
}

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