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 mxN = 111;
int arr[mxN];
int dist[mxN][mxN];
int numHub = 0;
int lcadist[mxN];
int n;
int s, t;
/*int indist[mxN][mxN];
int queries = 0;
int getDistance(int a, int b) {
queries++;
return indist[a][b];
}*/
int getdist(int a, int b) {
if(a==b)return 0;
if(dist[a][b]==-1) {
return dist[a][b] = dist[b][a] = getDistance(a, b);
}
return dist[a][b];
}
bool solve(int hub) {
vector<int> stk;
vector<int> dead;
int dsu[mxN];
int sz[mxN];
for(int i = 0; i < n; ++i) {
dsu[i] = i;
sz[i] = 1;
stk.push_back(i);
}
function<int(int)> find = [&](int a) {
return a==dsu[a] ? a : dsu[a] = find(dsu[a]);
};
function<void(int, int)> merge = [&](int a, int b) {
a = find(a); b = find(b);
if(a==b)return;
dsu[b] = a;
sz[a]+=sz[b];
};
while(stk.size() > 1) {
if(stk.size()&1) {
dead.push_back(stk.back());
stk.pop_back();
continue;
}
int first = stk.back();
stk.pop_back();
int second = stk.back();
stk.pop_back();
if(lcadist[first] < lcadist[hub] && lcadist[second] < lcadist[hub]) {
stk.push_back(first);
merge(first, second);
}else if(lcadist[first] > lcadist[hub] && lcadist[second] > lcadist[hub]) {
stk.push_back(first);
merge(first, second);
}else if(lcadist[first] == lcadist[hub] && lcadist[second] == lcadist[hub]) {
if(getdist(s, first) + getdist(s, second) - getdist(first, second) > 2 * lcadist[hub]) {
stk.push_back(first);
merge(first, second);
}else {
dead.push_back(first);
dead.push_back(second);
}
}else {
dead.push_back(first);
dead.push_back(second);
}
}
if(stk.size()) {
int maj = stk.back();
for(int k: dead) {
merge(maj, k);
}
if(sz[maj] > n/2)return false;
}
return true;
}
int hubDistance(int N, int sub) {
n = N;
memset(dist, -1, sizeof(dist));
for(int i = 1, mxdist = 0; i < n; ++i) {
if(getdist(0, i) > mxdist) {
mxdist = getdist(0, i);
s = i;
}
}
for(int i = 0, mxdist = 0; i < n; ++i) {
if(i^s) {
if(getdist(s, i) > mxdist) {
mxdist = getdist(s, i);
t = i;
}
}
}
int hub[2];
int hubcnt = 0;
int R = 0x3f3f3f3f;
for(int i = 0; i < n; ++i) {
lcadist[i] = (getdist(s, i) + getdist(s, 0) - getdist(i, 0)) / 2;
if(max(lcadist[i], getdist(s, t) - lcadist[i]) < R) {
R = max(lcadist[i], getdist(s, t) - lcadist[i]);
hubcnt = 1;
hub[0] = i;
}else if(max(lcadist[i], getdist(s, t) - lcadist[i]) == R){
hubcnt = 2;
hub[1] = i;
}
}
if(sub <= 2) {
return R;
}
bool balanced = false;
for(int i = 0; i < hubcnt; ++i) {
balanced |= solve(hub[i]);
}
return (balanced ? 1 : -1) * R;
}
/*int main() {
//freopen("disconnect.in", "r", stdin);
//freopen("file.out", "w", stdout);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
cin.tie(0)->sync_with_stdio(0);
return 0;
}*/
# | 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... |