# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
359798 | kylych03 | 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>
#include "grader.cpp"
using namespace std;
int d1[1000];
int d2[1000];
int hubDistance(int N, int sub) {
int mx = 0, u1, x , u2;
for(int i = 1; i < N; i++){
x = getDistance(0,i);
if(x > mx){
mx = x;
u1 = i;
}
}
d1[0]=mx;
mx = 0;
for(int i = 0; i < N; i++){
d1[i]=getDistance(u1,i);
if(d1[i] > mx){
mx = d1[i];
u2 = i;
}
}
d2[u1] = mx;
int diam = mx;
int res = diam;
for(int i = 0; i < N; i++){
d2[i]=getDistance(u2,i);
int len = (d1[i] + d2[i] - diam ) / 2;
len = d2[i] - len;
res = min(res, max(len, diam - len));
}
for(int i = 0 ; i < N ;i++)
d1[i] = d2[i] = 0;
return res;
}