Submission #1240387

#TimeUsernameProblemLanguageResultExecution timeMemory
1240387arman_ferdousSwapping Cities (APIO20_swap)C++20
0 / 100
45 ms9056 KiB
#include "swap.h" #ifdef DeBuG #include "debug.h" #else #include <bits/stdc++.h> #define dbg(...) #endif using namespace std; #define sz(v) (int)(v).size() #define all(v) v.begin(),v.end() #define rep(i,a,b) for (int i=(a);i<(b);++i) using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; using vi = vector<int>; template<class T> using V = vector<T>; const int N = 1e5+10; const int LG = __lg(N) + 1; const int oo = 2e9; V<int> g[N]; struct DSU { int n; V<pii> p, endpoints; V<int> nonbamboo; DSU (int _n = 0) : n(_n), p(n), endpoints(n), nonbamboo(n) { p.reserve(n + n); endpoints.reserve(n + n); nonbamboo.reserve(n + n); for (int i = 0; i < n; ++i) p[i] = {i, 0}, endpoints[i] = {i, i}; fill(all(nonbamboo), oo); } int find (int u) { if (p[u].first == u) return u; return p[u].first = find(p[u].first); } bool endpoints_merge (int u, int v, int U, int V) { if (u != endpoints[U].first && u != endpoints[U].second) return false; if (v != endpoints[V].first && v != endpoints[V].second) return false; return true; } void merge (int u, int v, int w) { int U = find(u), V = find(v); if (U == V) { nonbamboo[U] = min(nonbamboo[U], w); return; } g[n].push_back(U); g[n].push_back(V); p.emplace_back(n, w); endpoints.emplace_back(-1, -1); nonbamboo.emplace_back(min(nonbamboo[U], nonbamboo[V])); if (nonbamboo[n] == oo && endpoints_merge(u, v, U, V)) { endpoints[n].first = endpoints[V].first ^ endpoints[V].second ^ v; endpoints[n].second = endpoints[U].first ^ endpoints[U].second ^ u; } p[U].first = p[V].first = n++; } }dsu; int n, m; int lev[N], jmp[LG][N]; void dfs (int u) { for (int v : g[u]) { lev[v] = lev[u] + 1; jmp[0][v] = u; for (int j = 1; j < LG; ++j) jmp[j][v] = jmp[j - 1][jmp[j - 1][v]]; dfs(v); } } int lca (int u, int v) { if (lev[u] > lev[v]) swap(u, v); for (int j = LG - 1; j >= 0; --j) if (lev[v] - (1 << j) >= lev[u]) v = jmp[j][v]; if (u == v) return u; for (int j = LG - 1; j >= 0; --j) if (jmp[j][u] != jmp[j][v]) u = jmp[j][u], v = jmp[j][v]; return jmp[0][u]; } void init(int _N, int _M, vector<int> u, vector<int> v, vector<int> w) { n = _N, m = _M; dsu = DSU(n); V<int> ord(m); iota(all(ord), 0); sort(all(ord), [&](int i, int j) { return w[i] < w[j]; }); for (int i : ord) dsu.merge(u[i], v[i], w[i]); for (int j = 0; j < LG; ++j) jmp[j][dsu.n - 1] = dsu.n - 1; dfs(dsu.n - 1); } int getMinimumFuelCapacity(int X, int Y) { int u = lca(X, Y); if (dsu.endpoints[u].first != -1) { for (int j = LG - 1; j >= 0; --j) { if (dsu.endpoints[jmp[j][u]].first != -1) u = jmp[j][u]; } int ans = dsu.nonbamboo[u], v = dsu.p[u].first; if (v != u) ans = min(ans, dsu.p[v].second); if (ans == oo) ans = -1; return ans; } return dsu.p[u].second; }
#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...