#include "towns.h" #include <bits/stdc++.h> using namespace std; #define cerr if (false) cerr 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])); } cerr << "diam: " << diam1 << " -> " << diam2 << "\n"; map<int, vector<int>> distHorHubs; for (int i = 0; i < N; i++) { if (distHorHubs.find(distHor[i]) == distHorHubs.end()) { distHorHubs[distHor[i]] = {i}; } else { distHorHubs[distHor[i]].emplace_back(i); } } int cntLeft = 0, cntRight = 0; vector<Hub> hubs; bool foundHub = false; cerr << "size of sprouts: "; for (pair<int,vector<int>> infoSprout : distHorHubs) { if (infoSprout.second.empty()) continue; cerr << (int)infoSprout.second.size() << " "; 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(); } } cerr << "\n"; for (int i = 0; i < (int)hubs.size(); i++) { hubs[i].cntRight = cntRight; if ((int)hubs.size() > 1) { assert((int)hubs.size() == 2); if (i^1 < i) hubs[i].cntLeft += (int)hubs[i^1].nodes.size(); else hubs[i].cntRight += (int)hubs[i^1].nodes.size(); } } cerr << "hubs:\n"; for (Hub& hub : hubs) { cerr << " " << hub.cntLeft << " " << (int)hub.nodes.size() << " " << hub.cntRight << "\n"; if (max({hub.cntLeft, hub.cntRight, (int)hub.nodes.size()}) <= (N+1)/2) { cerr << minMax << "\n"; return minMax; } } cerr << -minMax << "\n"; return -minMax; }