Submission #743695

#TimeUsernameProblemLanguageResultExecution timeMemory
743695RushBSwapping Cities (APIO20_swap)C++17
100 / 100
447 ms57076 KiB
//happier ending for folks like us? //yani in AC nashe, yak yak kesaii ke in APIO dadan dast ma //PAIN #include "swap.h" #include <bits/stdc++.h> using namespace std; const int N = 4e5 + 15, M = 2e5 + 5, L = 21, INF = 0x3f3f3f3f; int p[N], dpr[N], pr[N][L], ext[N], P[N], h[N], rt, D[N], deg[N]; vector<int> adj[N], Wtmp; inline void smin(int &a, int b) {a = min(a, b);} void dfs(int v) { for (int i = 1; i < L; i++) pr[v][i] = pr[pr[v][i - 1]][i - 1]; for (auto u: adj[v]) { pr[u][0] = v; h[u] = h[v] + 1; dfs(u); smin(ext[v], ext[u]); } } int gpr(int u) {return dpr[u] == u ? u : dpr[u] = gpr(dpr[u]);} bool merge(int u, int v, int id) { int tu = u, tv = v; deg[tu]++, deg[tv]++; u = gpr(u), v = gpr(v); if (u == v) return false; dpr[u] = dpr[v] = id + M; D[id + M] = max({D[u], D[v], deg[tu], deg[tv]}); adj[id + M].push_back(u); adj[id + M].push_back(v); return true; } void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) { iota(p, p + m, 0); sort(p, p + m, [&](const int x, const int y) {return W[x] < W[y];}); iota(dpr, dpr + N, 0); memset(ext, 0x3f, sizeof ext); Wtmp = W; for (int i = 0; i < m; i++) { const int id = p[i]; if (!merge(U[id], V[id], id)) { smin(ext[U[id]], W[id]); smin(ext[V[id]], W[id]); } } rt = gpr(0), pr[rt][0] = rt, dfs(rt); } int LCA(int X, int Y) { for (int i = L - 1; i >= 0; i--) if (pr[Y][i] != pr[X][i]) Y = pr[Y][i], X = pr[X][i]; return pr[X][0]; } int getMinimumFuelCapacity(int X, int Y) { if (h[X] < h[Y]) swap(X, Y); while (h[Y] < h[X]) X = pr[X][__lg(h[X] - h[Y])]; int w = INF, lca = LCA(X, Y); for (int i = L - 1; i >= 0; i--) if (pr[Y][i] != pr[X][i] || D[pr[X][i]] <= 2) Y = pr[Y][i], X = pr[X][i]; smin(w, (D[pr[X][0]] > 2 ? Wtmp[pr[X][0] - M] : INF)); if (h[X] <= h[lca]) smin(w, max(Wtmp[X - M], ext[X])); return w >= INF ? -1 : w; }
#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...