#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> distv;
int n;
int dist(int a, int b){
if (a==b){return 0;}
if (a>b){
swap(a,b);
}
if (distv[a][b]!=-1){
return distv[a][b];
} else {
return distv[a][b]=getDistance(a,b);
}
}
int hubDistance(int N, int sub) {
n=N;
distv.assign(n,vector<int>(n,-1));
int adist = -1;
int aind = -1;
for (int i = 0; i<n; i++){
int ds = dist(0,i);
if (adist<ds){
adist=ds;
aind=i;
}
}
int bdist = -1;
int bind = -1;
for (int i = 0; i<n; i++){
int ds = dist(aind,i);
if (bdist<ds){
bdist=ds;
bind=i;
}
}
//from adist to aind
//vector<int> diameter;
int hubdist = 1e9;
int hubind = -1;
for (int i = 0; i<n; i++){
if (i==aind||i==bind){continue;}
int distfroma = dist(aind,i)-(dist(aind,i)+dist(bind,i)-dist(aind,bind))/2;
int rv = max(distfroma,dist(aind,bind)-distfroma);
if (rv<hubdist){
hubdist=rv;
hubind=i;
}
}
return -hubdist;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:48:9: warning: variable 'hubind' set but not used [-Wunused-but-set-variable]
int hubind = -1;
^~~~~~
towns.cpp:20:28: warning: unused parameter 'sub' [-Wunused-parameter]
int hubDistance(int N, int sub) {
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
512 KB |
Output is correct |
2 |
Correct |
16 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
23 ms |
384 KB |
Output is correct |
5 |
Correct |
21 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
384 KB |
Output is correct |
2 |
Correct |
17 ms |
384 KB |
Output is correct |
3 |
Correct |
21 ms |
460 KB |
Output is correct |
4 |
Correct |
21 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
22 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
20 ms |
624 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |