#include "towns.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)
bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }
/*
getDistance (i, j)
*/
vector<int> dA, dB, dp;
bool same (ll i, ll j) { return (getDistance(i, j) == dp[i] + dp[j]); }
struct DSU {
vll pa, szn;
DSU () { }
DSU (ll n): pa(n, 0), szn(n, 1) { fo (i, n) pa[i] = i; }
void add (ll par, ll siz) {
pa.pb(par);
szn.pb(siz);
}
ll find (ll i) { return (pa[i] == i ? i : find(pa[i])); }
void unite (ll a, ll b) {
ll ra = find(a), rb = find(b);
if (ra == rb) return;
if (szn[ra] < szn[rb]) swap(ra, rb);
szn[ra] += szn[rb];
pa[rb] = ra;
}
};
// si hay un elemento mayoritario este retornara su frecuencia
ll solve (vll &vec) {
vll alive, dead;
DSU gr(vec.size());
fo (i, vec.size()) alive.pb(i);
while (alive.size() > 1) {
vll nalive;
for (ll i = 0; i+1 < alive.size(); i += 2) {
if (same(vec[alive[i]], vec[alive[i+1]])) {
gr.unite(alive[i], alive[i+1]);
nalive.pb(alive[i]);
} else {
dead.pb(alive[i]);
dead.pb(alive[i+1]);
}
}
if (alive.size()&1) {
dead.pb(alive.back());
}
alive = nalive;
}
for (ll i: dead) {
if (same(vec[alive[0]], vec[i])) gr.unite(alive[0], i);
}
return gr.szn[gr.find(alive[0])];
}
int hubDistance(int N, int sub) {
int A = 0, B = 0, b = 0;
fore (i, 1, N) {
int g = getDistance (0, i);
if (g > b) {
b = g;
A = i;
}
}
dA = vector<int>(N, 0);
dB = vector<int>(N, 0);
dp = vector<int>(N, 0);
B = 0;
fo (i, N) {
if (i == A) continue;
int g = getDistance (A, i);
dA[i] = g;
if (g > b) {
b = g;
B = i;
}
}
int ans = dA[B], ok = -1;
fo (i, N) {
if (i == B) continue;
dB[i] = getDistance (B, i);
}
map<ll, vll> cnt;
fo (i, N) {
if (i == A || i == B) continue;
int d = dA[i] + dB[i] - dA[B];
d /= 2;
dp[i] = d;
cnt[dA[i] - d].pb(i);
ans = min(ans, max(dA[i], dB[i]) - d);
}
if (sub <= 2) return ans;
ll sum = 1;
for (auto [k, vec]: cnt) {
ll t = vec.size();
if (max(k, dA[B] - k) > ans) {
sum += t;
continue;
}
if (sum > N/2 || N - sum - t > N/2) {
sum += t;
continue;
}
if (t <= N/2) {
ok = 1;
break;
}
ll w = solve (vec);
if (w <= N/2) {
ok = 1;
break;
}
sum += t;
}
return ans * ok;
}
# | 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... |