Submission #1043824

#TimeUsernameProblemLanguageResultExecution timeMemory
1043824VMaksimoski008Swapping Cities (APIO20_swap)C++17
100 / 100
171 ms62148 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 5; const int LOG = 20; int par[maxn], C[maxn], deg[maxn], dp[maxn], P[maxn], ok[maxn], G[maxn], d[maxn], n, m, N, up[maxn][LOG]; vector<int> graph[maxn]; vector<array<int, 3> > edges; int find(int u) { if(u == par[u]) return u; return par[u] = find(par[u]); } void uni(int a, int b) { a = find(a); b = find(b); n++; if(a == b) C[n] = 1; par[n] = par[a] = par[b] = n; if(G[a] || G[b]) G[n] = 1; if(C[a] || C[b]) C[n] = 1; graph[n].push_back(a); if(a != b) graph[n].push_back(b); } void dfs(int u, int last) { for(int i=1; i<LOG; i++) up[u][i] = up[up[u][i-1]][i-1]; if(ok[u]) last = u; dp[u] = last; for(int &v : graph[u]) { d[v] = d[u] + 1; up[v][0] = u; P[v] = u; dfs(v, last); } } int get_lca(int a, int b) { if(d[a] < d[b]) swap(a, b); int D = d[a] - d[b]; for(int j=LOG-1; j>=0; j--) if(D & (1 << j)) a = up[a][j]; if(a == b) return a; for(int j=LOG-1; j>=0; j--) if(up[a][j] != up[b][j]) a = up[a][j], b = up[b][j]; return up[a][0]; } void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) { n = _N; N = _N; m = _M; for(int i=1; i<=_N+_M; i++) par[i] = i; for(int i=0; i<m; i++) edges.push_back({ W[i], U[i] + 1, V[i] + 1}); sort(edges.begin(), edges.end()); for(auto &[w, u, v] : edges) { deg[u]++; deg[v]++; if(deg[u] >= 3 || deg[v] >= 3) G[n+1] = 1; uni(u, v); } for(int i=1; i<=n; i++) ok[i] = (G[i] || C[i]); dfs(n, -1); } int getMinimumFuelCapacity(int X, int Y) { int L = get_lca(X+1, Y+1); if(dp[L] == -1) return -1; return edges[dp[L]-N-1][0]; }
#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...