Submission #961449

#TimeUsernameProblemLanguageResultExecution timeMemory
961449kilkuwuSwapping Cities (APIO20_swap)C++17
100 / 100
306 ms41688 KiB
#include "swap.h" #include <bits/stdc++.h> template <typename T> inline bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template <typename T> inline bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } constexpr int mxM = 200'000; constexpr int mxN = 100'000; constexpr int LOG = 20; constexpr int inf = 1e9 + 7; struct Edge { int u, v, w; bool operator<(const Edge& rhs) const { return w < rhs.w; } inline int other(int x) { return u ^ v ^ x; } }; Edge edges[mxM]; std::vector<std::pair<int, int>> adj[mxN]; int up[LOG][mxN]; int vv[LOG][mxN]; int dep[mxN]; int num_nodes; std::pair<int, int> par[mxN + mxM]; std::pair<int, int> find(int u) { if (par[u].first == -1) { return {u, par[u].second}; } auto pu = find(par[u].first); pu.second = std::min(pu.second, par[u].second); return par[u] = pu; } void merge(int u, int v, int w) { auto pu = find(u), pv = find(v); par[pu.first].first = par[pv.first].first = num_nodes; if (par[pu.first].second <= 1e9) { ckmin(par[num_nodes].second, w); } if (par[pv.first].second <= 1e9) { ckmin(par[num_nodes].second, w); } if (pu.first == pv.first) { ckmin(par[num_nodes].second, w); } else { adj[u].emplace_back(w, v); adj[v].emplace_back(w, u); } if (adj[u].size() > 2 || adj[v].size() > 2) { ckmin(par[num_nodes].second, w); } //std::cerr << u << " " << v << " " << w << " " << par[num_nodes].second << std::endl; num_nodes++; } void dfs(int u) { for (auto [w, v] : adj[u]) { if (v == up[0][u]) continue; dep[v] = dep[u] + 1; up[0][v] = u; vv[0][v] = w; dfs(v); } } void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) { for (int i = 0; i < N + M; i++) { par[i] = {-1, inf}; } num_nodes = N; for (int i = 0; i < M; i++) { edges[i] = {U[i], V[i], W[i]}; } std::sort(edges, edges + M); for (int i = 0; i < M; i++) { auto [u, v, w] = edges[i]; merge(u, v, w); } dfs(0); for (int k = 0; k + 1 < LOG; k++) { for (int i = 0; i < N; i++) { up[k + 1][i] = up[k][up[k][i]]; vv[k + 1][i] = std::max(vv[k][i], vv[k][up[k][i]]); } } } int max_path(int u, int v) { if (dep[u] > dep[v]) std::swap(u, v); int d = dep[v] - dep[u]; int ans = 0; for (int k = 0; k < LOG; k++) { if (d >> k & 1) { ckmax(ans, vv[k][v]); v = up[k][v]; } } if (u == v) return ans; for (int k = LOG - 1; k >= 0; k--) { if (up[k][u] != up[k][v]) { ckmax(ans, vv[k][u]); ckmax(ans, vv[k][v]); u = up[k][u]; v = up[k][v]; } } ckmax(ans, vv[0][u]); ckmax(ans, vv[0][v]); return ans; } int getMinimumFuelCapacity(int X, int Y) { int ans = std::min(find(X).second, find(Y).second); ans = std::max(ans, max_path(X, Y)); return ans <= 1e9 ? ans : -1; } /* 8 7 2 0 9 2 1 3 1 3 1 0 5 6 5 4 5 1 6 3 3 7 4 1 0 4 */
#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...