# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
718992 | Karuk | Towns (IOI15_towns) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,int>m;
int getmindist(int d1,int d2,int d3) {
int dd=(d1+d2-d3)/2;
int d=(d1+d3-d2)/2;
int ddd=(d2+d3-d1)/2;
return max(max(d,dd),ddd);
}
int hubDistance(int n,int sub) {
int maxd=0,maxind=0;
int md=0;
for(int i=1;i<n;i++) {
int p=getDistance(0,i);
m[{0,i}]=m[{i,0}]=p;
if(maxd<p) {
maxd=p;
maxind=i;
}
}
md=maxind;
maxd=0;
maxind=0;
for(int i=0;i<n;i++) {
if(i==md)continue;
int p=getDistance(md,i);
m[{md,i}]=m[{i,md}]=p;
if(maxd<p) {
maxd=p;
maxind=i;
}
}
int minr=INT_MAX;
for(int i=0;i<n;i++) {
if(i==md || i==maxind)continue;
minr=min(minr,getmindist(maxd,m[{i,md}],getDistance(i,maxind));
}
return minr;
}