Submission #610208

#	Time	Username	Problem	Language	Result	Execution time	Memory
610208		Temmie	Towns (IOI15_towns)	C++17	25 / 100	19 ms	400 KiB

towns

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

int hubDistance(int n, int sub) {
	std::vector <std::vector <int>> am(n, std::vector <int> (n, 0));
	for (int i = 0; i < n; i++) {
		am[i][i] = 0;
	}
	int u = -1, v = -1;
	for (int i = 1; i < n; i++) {
		am[0][i] = am[i][0] = getDistance(0, i);
		if (u == -1 || am[0][i] > am[0][u]) {
			u = v = i;
		}
	}
	for (int i = 0; i < n; i++) {
		am[u][i] = am[i][u] = getDistance(u, i);
		if (am[u][i] > am[u][v]) {
			v = i;
		}
	}
	int ans = 1 << 30;
	int a = -1;
	std::vector <int> b(n);
	std::pair <int, int> p = { ans, ans };
	for (int i = 0; i < n; i++) {
		b[i] = am[u][i] - am[0][i] + am[0][u];
		b[i] >>= 1;
		ans = std::min(ans, std::max(b[i], am[u][v] - b[i]));
		if (i && i != u) {
			p = { std::min(p.first, b[i]), std::max(p.second, b[i]) };
		}
	}
	for (int i = 0; i < n; i++) {
		if (ans != std::max(b[i], am[u][v] - b[i])) {
			continue;
		}
		int x = 0, y = 0;
		for (int j = 0; j < n; j++) {
			if (b[j] > b[i]) {
				y += b[j] != b[i];
			} else {
				x += b[j] != b[i];
			}
		}
		a = std::max(x, y) <= (n >> 1) ? i : a;
	}
	if (a == -1) {
		return -ans;
	}
	b[u] = p.first;
	b[0] = p.second;
	am[u][u] = b[u] << 1;
	int res = 0;
	int last = 0;
	std::vector <int> inc(n, 0);
	std::vector <bool> no(n, false);
	for (int i = 0; i < n; i++) {
		if (b[i] != b[a]) {
			continue;
		}
		if (res == 0) {
			for (int j = 0; j < n; j++) {
				no[j] = false;
			}
			last = i;
		}
		if (i == last && getDistance(i, last) < am[u][i] + am[u][last] - (b[a] << 1)) {
			inc[last]++;
		} else {
			inc[i] = no[i] = true;
		}
	}
	for (int i = 0; i < n; i++) {
		res += inc[i] * (!no[i] && inc[i] && (i == last && getDistance(i, last) < am[u][i] + am[u][last] + (b[a] << 1)));
	}
	return res <= (n >> 1) ? ans : -ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:4:28: warning: unused parameter 'sub' [-Wunused-parameter]
    4 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~

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