# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
387402 | alishahali1382 | 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;
typedef long long ll;
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
const int mod=1000000007;
const int N=120;
int n, m, k, ans;
int D[N][N];
int ask(int i, int j){
if (i==j) return 0;
if (i>j) swap(i, j);
if (D[i][j]==-1) D[i][j]=getDistance(i, j);
return D[i][j];
}
int hubDistance(int n, int sub){
memset(D, -1, sizeof(D));
int X=0, Y=0;
for (int i=1; i<n; i++) if (ask(0, i)>ask(0, X)) X=i;
for (int i=1; i<n; i++) if (ask(X, i)>ask(X, Y)) Y=i;
ans=inf;
for (int i=0; i<n; i++){
int a=(ask(X, i)+ask(X, Y)-ask(Y, i))/2;
int b=ask(X, Y)-a, c=ask(X, i)-a;
ans=min(ans, max(a, b));
}
return ans;
}