# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
28087 | 2017-07-15T10:21:50 Z | noobprogrammer | Towns (IOI15_towns) | C++14 | 0 ms | 0 KB |
#include "towns.h" #include <bits/stdc++.h> using namespace std ; #define vi vector<int> int from[105] , to[105] ; vii len[1000010] ; int hubDistance(int n, int sub) { int mdist = -1 , opt = -1 , tmp ; for(int i=0;i<n;i++){ tmp = getDistance(0 , i) ; if(mdist < tmp){ mdist = tmp ; opt = i ; } } mdist = -1 ; int nxt = -1 ; for(int i=0;i<n;i++){ from[i] = getDistance(opt , i) ; if(from[i] > mdist){ mdist = from[i] ; nxt = i; } } for(int i=0;i<n;i++) to[i] = getDistance(nxt , i ) ; for(int i=1;i<=1000000;i++) len[i].clear() ; int res = 1e9 ; for(int i=0;i<n;i++){ if(i == nxt ||i == opt) continue ; int ok = (from[i] + to[i] - mdist)/2 ; int ln = from[i] - ok ; len[ln].push_back({i , ok }) ; res = min(res , max( mdist - ln , ln ) ) ; } return res ; }