#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu{
vector<int>root;
vector<int>siz;
int mxsiz=1;
dsu(int n){
root=vector<int>(n);
iota(root.begin(),root.end(),0);
siz=vector<int>(n,1);
}
int findRoot(int x){
if(x==root[x])
return x;
return root[x]=findRoot(root[x]);
}
bool unite(int x, int y){
x=findRoot(x);
y=findRoot(y);
if(x==y)
return 0;
if(siz[x]<siz[y])
swap(x,y);
siz[x]+=siz[y];
root[y]=x;
mxsiz=max(mxsiz,siz[x]);
return 1;
}
};
int hubDistance(int n, int sub) {
int dists[n];
dists[0]=0;
for(int i = 1;i<n;i++){
dists[i] = getDistance(0,i);
}
int u = max_element(dists,dists+n)-dists;
dists[u]=0;
for(int i = 0;i<n;i++){
if(i==u)
continue;
dists[i]=getDistance(u,i);
}
int v = max_element(dists,dists+n)-dists;
int ans = dists[v];
map<int,vector<int>>mp;
int rds[n];
int cds[n];
for(int i = 0;i<n;i++){
int d = getDistance(i,v);
int cd = (dists[i]+dists[v]-d)/2;
int rd = (dists[i]+d-dists[v])/2;
cds[i]=cd;
rds[i]=rd;
mp[cd].push_back(i);
cd=max(cd,dists[v]-cd);
ans=min(ans,cd);
}
bool wor = 0;
int beh = 0;
for(pair<int,vector<int>>p:mp){
if(p.first==ans||p.first==dists[v]-ans){
if(beh<=n/2&&(n-beh-p.second.size())<=n/2){
dsu ds(n);
for(int i : p.second){
for(int j : p.second){
if(j<=i)
continue;
if(getDistance(i,j)<rds[i]+rds[j]){
ds.unite(i,j);
}
}
}
if(ds.mxsiz<=n/2){
wor=1;
break;
}
}
}
beh+=p.second.size();
}
if(!wor){
ans=-ans;
}
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... |