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>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;
const int N = 120;
int dis0[N], disa[N], disb[N];
int dis[N][N];
int cnt;
namespace dsu {
int par[N];
int sz[N];
void init() {
fill(par, par+N, -1);
fill(sz, sz+N, 1);
}
int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
void unite(int v, int u) {
//v = rt(v);
//u = rt(u);
//if (sz[v] < sz[u])
// swap(v, u);
sz[v] += sz[u];
par[u] = v;
}
}
int get(int i, int j)
{
if (i == j)
return 0;
if (i > j)
swap(i, j);
if (!dis[i][j]) {
++cnt;
dis[i][j] = getDistance(i, j);
}
return dis[i][j];
}
int get2(int a, int v, int b)
{
return (get(a, v) + get(a, b) - get(v, b))/2;
}
int find_hub(int a, int b, int n, int r)
{
if (get(a, b) == r*2)
return r;
bool x = 0, y = 0;
vector<int> X, Y;
Loop (i,0,n) {
if (get2(a, i, b) == r)
x = 1;
if (get2(b, i, a) == r)
y = 1;
(get(a, i) < get(b, i)? Y: X).push_back(i);
}
if (!x)
return get(a, b) - r;
if (!y)
return r;
if (X.size()*2 > n)
return r;
if (X.size()*2 == n)
return -1;
return get(a, b) - r;
}
mt19937_64 rd(time(0));
int sel(const vector<int> &val)
{
int sum = accumulate(val.begin(), val.end(), 0);
int x = rd() % sum;
Loop (i,0,val.size()) {
if (x < val[i])
return i;
x -= val[i];
}
assert(false);
}
int hubDistance(int n, int sub) {
memset(dis, 0, sizeof(dis));
cnt = 0;
Loop (i,0,n)
dis0[i] = get(0, i);
int a = max_element(dis0, dis0+n) - dis0;
Loop (i,0,n)
disa[i] = get(a, i);
int b = max_element(disa, disa+n) - disa;
Loop (i,0,n)
disb[i] = get(b, i);
int ans = 1e9;
Loop (i,0,n) {
int x = (disa[i] + disa[b] - disb[i])/2;
int y = (disb[i] + disb[a] - disa[i])/2;
ans = min(ans, max(x, y));
}
int v = find_hub(a, b, n, ans);
if (v == -1)
return ans;
vector<int> L, M, R;
Loop (i,0,n) {
(get2(a, i, b) < v? L:
get2(a, i, b) > v? R:
M).push_back(i);
}
if (L.size()*2 > n || R.size()*2 > n)
return -ans;
if (M.size()*2 <= n)
return ans;
//cout << a << ' ' << b << '\n';
//for (int x : M)
// cout << x << ' ';
//cout << '\n';
for (int x : M) {
int sz = 1;
for (int y : M) {
if (x == y || get2(x, a, b) + get2(y, a, b) == get(x, y))
continue;
sz++;
}
if (sz*2 > n)
return -ans;
}
//dsu::init();
//for (int x : M) for (int y : M) {
// x = dsu::rt(x);
// y = dsu::rt(y);
// if (x == y || get2(x, a, b) + get2(y, a, b) == get(x, y))
// continue;
// dsu::unite(x, y);
// //cout << x << ' ' << y << " -> " << dsu::sz[x] << '\n';
// if (dsu::sz[x]*2 > n)
// return -ans;
//}
//for (int dard = 0; sub >= 3 && dard < 200000 && cnt < 5*n; ++dard) {
// vector<int> vec, sz;
// for (int v : M) {
// if (dsu::par[v] != -1)
// continue;
// vec.push_back(v);
// sz.push_back(dsu::sz[v] * dsu::sz[v]);
// }
// //int x = dsu::rt(M[rd()%M.size()]);
// int y = dsu::rt(M[rd()%M.size()]);
// int x = sel(sz);
// x = vec[x];
// //vector<int> vec;
// //for (int v : M) {
// // int r = rt(v);
// // if (r != x)
// // vec.push_back(r);
// //}
// //int y = vec[rd()%vec.size()];
// if (x == y || get2(x, a, b) + get2(y, a, b) == get(x, y))
// continue;
// dsu::unite(x, y);
// //cout << x << ' ' << y << " -> " << dsu::sz[x] << '\n';
// if (dsu::sz[x]*2 > n)
// return -ans;
//}
return ans;
}
Compilation message (stderr)
towns.cpp: In function 'int find_hub(int, int, int, int)':
towns.cpp:58:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
58 | if (get2(a, i, b) == r)
| ^
towns.cpp:60:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
60 | if (get2(b, i, a) == r)
| ^
towns.cpp:62:11: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
62 | (get(a, i) < get(b, i)? Y: X).push_back(i);
| ^
towns.cpp:62:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
62 | (get(a, i) < get(b, i)? Y: X).push_back(i);
| ^
towns.cpp:62:43: warning: conversion from 'll' {aka 'long long int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
62 | (get(a, i) < get(b, i)? Y: X).push_back(i);
| ^
towns.cpp:68:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
68 | if (X.size()*2 > n)
| ~~~~~~~~~~~^~~
towns.cpp:70:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
70 | if (X.size()*2 == n)
| ~~~~~~~~~~~^~~~
towns.cpp: In function 'int sel(const std::vector<int>&)':
towns.cpp:79:15: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
79 | int x = rd() % sum;
| ~~~~~^~~~~
towns.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
| ^
towns.cpp:80:2: note: in expansion of macro 'Loop'
80 | Loop (i,0,val.size()) {
| ^~~~
towns.cpp:82:11: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
82 | return i;
| ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:92:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
92 | dis0[i] = get(0, i);
| ^
towns.cpp:93:36: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
93 | int a = max_element(dis0, dis0+n) - dis0;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:95:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
95 | disa[i] = get(a, i);
| ^
towns.cpp:96:36: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
96 | int b = max_element(disa, disa+n) - disa;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:98:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
98 | disb[i] = get(b, i);
| ^
towns.cpp:110:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
110 | (get2(a, i, b) < v? L:
| ^
towns.cpp:111:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
111 | get2(a, i, b) > v? R:
| ^
towns.cpp:112:36: warning: conversion from 'll' {aka 'long long int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
112 | M).push_back(i);
| ^
towns.cpp:114:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
114 | if (L.size()*2 > n || R.size()*2 > n)
| ~~~~~~~~~~~^~~
towns.cpp:114:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
114 | if (L.size()*2 > n || R.size()*2 > n)
| ~~~~~~~~~~~^~~
towns.cpp:116:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
116 | if (M.size()*2 <= n)
| ~~~~~~~~~~~^~~~
towns.cpp:88:28: warning: unused parameter 'sub' [-Wunused-parameter]
88 | 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... |