#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pll;
#define X first
#define Y second
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const int MAXN = 1e6 + 10;
int n, f[MAXN];
inline int get(int u, int v) {
u--, v--;
return getDistance(u, v);
}
inline pll diam_t(int v) {
int ans = v, ans_val = 0;
for (int i = 1; i <= n; i++) {
if (i == v) continue;
int t = get(v, i);
f[i] = t;
if (t > ans_val)
ans = i, ans_val = t;
}
return {ans, ans_val};
}
int hubDistance(int N_, int sub) {
n = N_;
int diam_v = diam_t(1).X;
auto [diam_u, diam] = diam_t(diam_v);
int r = numeric_limits<int>::max();
map<int, int> mp;
for (int i = 1; i <= n; i++) {
if (i == diam_u || i == diam_v) continue;
int du = get(diam_u, i);
int dv = f[i];
mp[du - dv]++;
int diff = max(du, dv) - min(du, dv);
int a = (diff + diam) / 2;
r = min(r, a);
}
int tr = 2 * r - diam;
int ps = 0;
int ss = n;
for (auto [x, y] : mp) {
ss -= y;
if (x == r || x == tr)
if (ps <= n / 2 && ss <= n / 2 && y <= n / 2)
return r;
ps += y;
}
return -r;
}
Compilation message
sorting.cpp:1:10: fatal error: towns.h: No such file or directory
1 | #include "towns.h"
| ^~~~~~~~~
compilation terminated.
