#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
int mem[111][111];
int ask(int i, int j) {
if (i==j) return 0;
if (mem[i][j]) return mem[i][j];
mem[i][j] = mem[j][i] = getDistance(i, j);
return mem[i][j];
}
struct DSU {
vector<int> p,sz;
DSU(int n) {
for(int i=0; i<n; ++i) p.pb(i),sz.pb(1);
}
int get(int u) {
return (p[u]==u)?u:get(p[u]);
}
void uni(int u, int v) {
u=get(u), v=get(v);
if (u==v) return;
if (sz[u]<sz[v]) swap(u,v);
p[v]=u;
sz[u]+=sz[v];
}
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int hubDistance(int n, int ilyashevchenko1love) {
for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) mem[i][j]=0;
vector<int> d0(n), dr(n);
int r=1;
for(int i=1; i<n; ++i) {
d0[i] = ask(0,i);
if (d0[i] > d0[r]) r=i;
}
int l=0;
for(int i=0; i<n; ++i) {
dr[i] = ask(r,i);
if (dr[i] > dr[l]) l=i;
}
int diam = dr[l];
map<int,vector<int>> m;
if (l==0) {
for(int i=0; i<n; ++i) {
int z = (d0[i]+dr[i]-diam)>>1;
m[dr[i]-z].pb(i);
}
} else {
int z0 = (d0[l]+d0[r]-diam)>>1;
int dr0 = dr[0]-z0;
m[dr0].pb(0);
for(int i=1; i<n; ++i) {
if (i==l) {
m[diam].pb(i); continue;
}
if (i==r) {
m[0].pb(i); continue;
}
int z = (d0[i] + dr[i] - d0[r])>>1;
if (dr[i]-z < dr0) {
m[dr[i]-z].pb(i);
} else if (dr[i]-z == dr0) {
m[dr0].pb(i);
} else {
m[dr0].pb(i);
}
}
}
int ans=diam;
for(auto&x:m) {
ans=min(ans,max(x.f,diam-x.f));
}
int left=0,right=n;
for(auto&x:m) {
int z = max(x.f, diam-x.f);
int sz = x.s.size();
right-=sz;
if (z==ans) if (max({left,right,sz}) <= n/2) return ans;
left+=sz;
}
left=0,right=n;
for(auto&x:m) {
int z = max(x.f, diam-x.f);
int sz = x.s.size();
right-=sz;
if (z==ans) if (max(left,right) <= n/2) {
vector<pi> a,b;
for(auto&v:x.s) a.pb({v,1});
//shuffle(a.begin(), a.end(), rng);
DSU dsu(n);
vector<int> ban(n);
vector<vector<int>> adj(n);
for(auto&it:a) {
int u=it.f;
if (!b.size()) {
b.pb({1,u}); continue;
}
int v=b.back().s;
int fx = dr[u] - x.f;
int fy = dr[v] - x.f;
int fz = ask(u,v);
//cout<<"> "<<dr[u]<<" "<<dr[v]<<" "<<x.f<<'\n';
//cout<<"??? "<<u<<' '<<v<<' '<<fx<<' '<<fy<<' '<<fz<<'\n';
if (fz < fx+fy) {b.back().f++; dsu.uni(u,v);}
else {
b.pb({1,u});
if (b.size()>=2) {
adj[b[b.size()-1].s].pb(b[b.size()-2].s);
adj[b[b.size()-2].s].pb(b[b.size()-1].s);
}
}
}
//for(auto&x:b) cout<<x.f<<','<<x.s<<" "; cout<<'\n';
sort(b.begin(), b.end());
vector<int> dp(b.size()+1);
for(int i=0; i<b.size(); ++i) {
//cout<<b[i].f<<' '<<b[i].s<<" "; for(auto&x:adj[b[i].s]) cout<<x<<' '; cout<<'\n';
dp[i+1] = max(dp[i],b[i].f);
for(int j=i-1; j>=0; --j) {
int bad=0;
for(auto&x:adj[b[i].s]) bad|=x==b[j].s;
if (bad) continue;
dp[i+1] = max(dp[i+1], dp[j+1]+b[i].f);
break;
}
}
//for(int i=0; i<b.size()+1; ++i) cout<<dp[i]<<' '; cout<<'\n';
if (dp[b.size()] <= n/2) return ans;
int tot = b.back().f;
int rt = b.back().s;
//cout<<"! "<<rt<<' '<<tot<<'\n';
for(int i=b.size()-2; i>=0; --i) {
if (dp[i+1] + tot <= n/2) return ans;
if (tot>=n/2) return -ans;
//cout<<b[i].f<<' '<<b[i].s<<' '<<tot<<'\n';
int bad=0;
for(auto&x:adj[b[i].s]) {
bad|=dsu.get(x) == dsu.get(rt);
}
if (bad) continue;
int u=b[i].s;
int fx = dr[u] - x.f;
int fy = dr[rt] - x.f;
int fz = ask(u,rt);
if (fz < fx+fy) {
dsu.uni(u,rt);
tot+=b[i].f;
}
}
}
left+=sz;
}
return -ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |