Submission #296033

#TimeUsernameProblemLanguageResultExecution timeMemory
296033Alexa2001Swapping Cities (APIO20_swap)C++17
100 / 100
279 ms20172 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; const int inf = 1e9 + 5; const int Nmax = 1e5 + 5; int rang[Nmax], t[Nmax], A[Nmax], B[Nmax], up[Nmax], good[Nmax], level[Nmax]; bool chain[Nmax]; int n, m; vector<int> v[Nmax]; int boss(int x) { if(x == t[x]) return x; return boss(t[x]); } bool endpoints(int x, int y, int a, int b) { //assert(boss(a) == x && boss(b) == y); assert(chain[x] && chain[y]); return (A[x] == a || B[x] == a) && (A[y] == b || B[y] == b); } void combine_chains(int x, int y, int a, int b) { B[y] = (A[y] == b ? B[y] : A[y]); A[y] = (A[x] == a ? B[x] : A[x]); } void dfs(int node) { for(auto it : v[node]) { good[it] = min(good[it], max(good[node], up[it])); level[it] = level[node] + 1; dfs(it); } } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { n = N; m = M; vector<int> ord(m); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&] (int x, int y) { return W[x] < W[y]; } ); for(int j = 0; j<n; ++j) { good[j] = inf; chain[j] = 1; A[j] = B[j] = j; rang[j] = 0; t[j] = j; } for(auto i : ord) { int x = U[i], y = V[i], cost = W[i]; x = boss(x); y = boss(y); if(x == y) { good[x] = min(good[x], cost); chain[x] = 0; continue; } if(rang[x] > rang[y]) { swap(x, y); swap(U[i], V[i]); } if(rang[x] == rang[y]) ++rang[y]; t[x] = y; v[y].push_back(x); up[x] = cost; if(chain[y]) { if(!chain[x] || (chain[x] && !endpoints(x, y, U[i], V[i]))) chain[y] = 0, good[y] = min(good[y], cost); else combine_chains(x, y, U[i], V[i]); } } dfs(boss(0)); } int getMinimumFuelCapacity(int x, int y) { int ans = 0; while(x != y) { if(level[x] > level[y]) ans = max(ans, up[x]), x = t[x]; else ans = max(ans, up[y]), y = t[y]; } ans = max(ans, good[x]); if(ans == inf) return -1; return ans; }
#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...