#include "towns.h"
#include <algorithm>
#include <cassert>
#include <limits>
#include <vector>
int hubDistance(int N, int) {
std::vector<int> distances_from_0(N);
for (int i = 1; i < N; i++) {
distances_from_0[i] = getDistance(0, i);
}
int u = std::max_element(distances_from_0.begin(), distances_from_0.end()) -
distances_from_0.begin();
std::vector<int> distances_from_u(N);
distances_from_u[0] = distances_from_0[u];
for (int i = 1; i < N; i++) {
if (i == u)
continue;
distances_from_u[i] = getDistance(u, i);
}
int v = std::max_element(distances_from_u.begin(), distances_from_u.end()) -
distances_from_u.begin();
int diameter = distances_from_u[v];
// y = connection point from [i] to 0u path.
std::vector<int> distance_y_to_u(N);
for (int i = 0; i < N; i++) {
distance_y_to_u[i] =
(distances_from_u[i] + distances_from_0[u] - distances_from_0[i]) / 2;
}
int radius = std::numeric_limits<int>::max();
for (int i = 0; i < N; i++) {
// if both on 0u and vu path
if (distance_y_to_u[i] <= distance_y_to_u[v]) {
int r = std::max(distance_y_to_u[i], diameter - distance_y_to_u[i]);
if (r < radius)
radius = r;
}
}
int max_size = N / 2;
int distance_center_u = -1;
int distance_other_center_u = -1;
for (int i = 0; i < N; i++) {
int dist = distance_y_to_u[i];
if (dist == radius)
distance_center_u = dist;
else if (dist == diameter - radius)
distance_other_center_u = dist;
}
if (distance_center_u == -1) {
distance_center_u = distance_other_center_u;
} else if (distance_other_center_u != -1) {
assert(distance_center_u > distance_other_center_u);
int subtree_size_center = 0;
for (int i = 0; i < N; i++) {
if (distance_y_to_u[i] >= distance_center_u) {
subtree_size_center++;
}
}
if (subtree_size_center * 2 == N) {
return radius;
} else if (subtree_size_center * 2 < N) {
distance_center_u = distance_other_center_u;
}
}
// From here on, distance_center_u is the only possible candidate.
std::vector<int> connected_to_x;
int connected_before_x = 0;
int connected_after_x = 0;
for (int i = 0; i < N; i++) {
if (distance_y_to_u[i] < distance_center_u) {
connected_before_x++;
} else if (distance_y_to_u[i] > distance_center_u) {
connected_after_x++;
} else {
connected_to_x.push_back(i);
}
}
if (connected_before_x > max_size || connected_after_x > max_size ||
connected_to_x.size() > max_size) {
return -radius;
}
return radius;
}
