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;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
map<pii, int> memo;
int dist(int u, int v) {
if (!memo[{u, v}]) {
memo[{u, v}] = memo[{v, u}] = getDistance(u, v);
}
return memo[{u, v}];
}
int hubDistance(int n, int sub) {
int res = 1000000000;
int furthest = 1, maxdist = dist(0, 1);
ffor(i, 2, n) {
if (dist(0, i) > maxdist) {
maxdist = dist(0, i);
furthest = i;
}
}
int furthest2 = 0;
maxdist = dist(furthest, 0);
ffor(i, 1, n) {
if (i != furthest && dist(furthest, i) > maxdist) {
maxdist = dist(furthest, i);
furthest2 = i;
}
}
map<int, int> xs;
ffor(j, 1, n) {
if (j == furthest2) {
continue;
}
int a = dist(furthest, furthest2), b = dist(furthest2, j), c = dist(furthest, j);
int x = (a + c - b) / 2, y = (b + c - a) / 2;
xs[x] = max(xs[x], y);
}
forin(p, xs) {
int curr = max(max(p.second, p.first), dist(furthest, furthest2) - p.first);
forin(p2, xs) {
if (p != p2) {
curr = max(curr, abs(p2.first - p.first) + p2.second);
}
}
res = min(res, curr);
}
return res;
}
Compilation message (stderr)
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:37:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
37 | if (dist(0, i) > maxdist) {
| ^
towns.cpp:38:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
38 | maxdist = dist(0, i);
| ^
towns.cpp:39:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
39 | furthest = i;
| ^
towns.cpp:45:39: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
45 | if (i != furthest && dist(furthest, i) > maxdist) {
| ^
towns.cpp:46:29: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
46 | maxdist = dist(furthest, i);
| ^
towns.cpp:47:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
47 | furthest2 = i;
| ^
towns.cpp:56:58: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
56 | int a = dist(furthest, furthest2), b = dist(furthest2, j), c = dist(furthest, j);
| ^
towns.cpp:56:81: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
56 | int a = dist(furthest, furthest2), b = dist(furthest2, j), c = dist(furthest, j);
| ^
towns.cpp:32:28: warning: unused parameter 'sub' [-Wunused-parameter]
32 | 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... |