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;
int hubDistance(int N, int sub) {
map<int,int> d[N];
auto get = [&](int a,int b){
if(a > b)
swap(a,b);
if(d[a].count(b))
return d[a][b];
if(a == b)
return 0;
return d[a][b] = getDistance(a,b);
};
int v = 0;
for(int i = 0;i<N;i++){
if(get(0,i) > get(0,v)){
v = i;
}
}
int x = 0;
for(int i = 0;i<N;i++){
if(get(v,i) > get(v,x)){
x = i;
}
}
int len = get(v,x);
// cout << v << ' ' << x << ' ' << len << endl;
map<int,vector<int>> mp;
for(int i = 0;i<N;i++){
int val = (get(0,i) + get(0,v) - get(v,i))/2;
mp[val].push_back(i);
}
int val1 = 0;
int val2 = 2e9;
int ans;
for(auto u:mp){
int tmp = get(0,v) - u.first;
// cout << tmp << endl;
if(tmp <= len/2){
val1 = max(val1,tmp);
}
if((len + 1)/2 <= tmp){
val2 = min(val2,tmp);
}
}
// cout << val1 << ' ' << val2 << endl;
ans = len - val1;
if(val2 != len - val1){
if(val2 < len - val1){
ans = val2;
val1 = -1;
}
else val2 = -1;
}
return -ans;
}
Compilation message (stderr)
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:4:28: warning: unused parameter 'sub' [-Wunused-parameter]
4 | int hubDistance(int N, int sub) {
| ~~~~^~~
# | 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... |