#include "towns.h" #include <bits/stdc++.h> using namespace std; const int OO = (int)1e18; struct Hub { vector<int> nodes; int cntLeft, cntRight; }; int hubDistance(int N, int subtask) { int maxDist = 0, diam1 = 0; for (int i = 1; i < N; i++) { int distOn = getDistance(0, i); if (distOn > maxDist) { maxDist = distOn, diam1 = i; } } vector<int> distDiam1(N, 0); for (int i = 0; i < N; i++) { distDiam1[i] = getDistance(diam1, i); } int diam2 = max_element(distDiam1.begin(), distDiam1.end()) - distDiam1.begin(); vector<int> distDiam2(N, 0); for (int i = 0; i < N; i++) { distDiam2[i] = getDistance(diam2, i); } vector<int> distHor(N, 0), distVert(N, 0); // from diam1 int minMax = OO; for (int i = 0; i < N; i++) { assert(!((distDiam1[diam2] + distDiam2[i] - distDiam1[i])&1)); distHor[i] = (distDiam1[diam2] + distDiam2[i] - distDiam1[i]) / 2; assert(!((3*distDiam2[i] - distDiam1[diam2] - distDiam1[i])&1)); distVert[i] = (3*distDiam2[i] - distDiam1[diam2] - distDiam1[i]) / 2; minMax = min(minMax, max(distHor[i], distDiam1[diam2] - distHor[i])); } map<int, vector<int>> distHorHubs; for (int i = 0; i < N; i++) { if (max(distHor[i], distDiam1[diam2] - distHor[i]) == minMax) { distHorHubs[distHor[i]].emplace_back(i); } } int cntLeft = 0, cntRight = 0; vector<Hub> hubs; bool foundHub = false; for (pair<int,vector<int>> infoSprout : distHorHubs) { if (infoSprout.second.empty()) continue; int maxDistHor = max(infoSprout.first, distDiam1[diam2] - infoSprout.first); if (maxDistHor == minMax) { hubs.emplace_back(Hub{infoSprout.second, cntLeft, 0}); foundHub = true; } else if (!foundHub) { cntLeft += (int)infoSprout.second.size(); } else if (foundHub) { cntRight += (int)infoSprout.second.size(); } } for (int i = 0; i < (int)hubs.size(); i++) { hubs[i].cntRight = cntRight; if ((int)hubs.size() > 1) { assert((int)hubs.size() == 2); hubs[i].cntRight += (int)hubs[i^1].nodes.size(); } } for (Hub& hub : hubs) { if (max({hub.cntLeft, hub.cntRight, (int)hub.nodes.size()}) < (N+1)/2) { return minMax; } } return -minMax; }