Submission #1217125

#TimeUsernameProblemLanguageResultExecution timeMemory
1217125LemserTowns (IOI15_towns)C++20
13 / 100
10 ms328 KiB
#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(alive[0], 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); } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...