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;
const int inf = 1e6 + 42;
int n;
vector<vector<int> > storedist;
int dist(int a, int b) {
if(storedist[a][b] != -1) {
return storedist[a][b];
}
return storedist[a][b] = storedist[b][a] = getDistance(a - 1, b - 1);
}
void reset() {
storedist.clear();
storedist.assign(1 + n, vector<int> (1 + n, -1));
for(int i = 1; i <= n; i++) {
storedist[i][i] = 0;
}
}
int hubDistance(int N, int sub) {
n = N;
reset();
int ans = inf;
int X = 1;
for(int i = 2; i <= n; i++) {
if(dist(1, i) > dist(1, X)) {
X = i;
}
}
int Y = X;
for(int i = 1; i <= n; i++) {
if(dist(X, i) > dist(X, Y)) {
Y = i;
}
}
int diam = dist(X, Y);
for(int i = 1; i <= n; i++) {
int a = dist(i, X);
int b = dist(i, Y);
int from = (a + b - diam) / 2;
ans = min(ans, max(a - from, b - from));
}
bool from_X = false, from_Y = false;
for(int i = 1; i <= n; i++) {
if(i == X || i == Y) {
continue;
}
int a = dist(i, X);
int b = dist(i, Y);
int from = (a + b - diam) / 2;
if(a - from == ans) {
from_X = true;
} else if(b - from == ans) {
from_Y = true;
}
}
vector<int> Z = {X, Y};
int idx = 0;
if(from_Y) {
idx = 1;
}
set<int> s;
int less_cnt = 0, more_cnt = 0;
for(int i = 1; i <= n; i++) {
int a = dist(i, X);
int b = dist(i, Y);
int from = (a + b - diam) / 2;
vector<int> d = {a - from, b - from};
if(d[idx] == ans) {
s.insert(i);
}
if(d[idx] < ans) {
less_cnt++;
}
if(d[idx] > ans) {
more_cnt++;
}
}
if(less_cnt > n / 2 || more_cnt > n / 2) {
return -ans;
}
if(from_X && from_Y) {
return ans;
}
vector<int> di(1 + n, 0);
for(int i : s) {
int a = dist(i, X);
int b = dist(i, Y);
int from = (a + b - diam) / 2;
di[i] = from;
}
for(int i : s) {
for(int j : s) {
int dij = dist(i, j);
int cnt = 0;
if(dij < di[i] + di[j]) {
cnt++;
}
if(cnt > n / 2) {
return -ans;
}
}
}
return ans;
}
Compilation message (stderr)
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:25:28: warning: unused parameter 'sub' [-Wunused-parameter]
25 | 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... |