제출 #1198136

#제출 시각아이디문제언어결과실행 시간메모리
1198136Blistering_BarnaclesSwapping Cities (APIO20_swap)C++20
100 / 100
252 ms44556 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; int n, m; const int N = (int)2e5 + 5; vector<pair<int, int>> adj[N]; int mx[18][N], dp[18][N], dep[N], dis[N], dis2[N]; pair<int, int> kth(int v, int k) { int ret = 0; for (int j = 0; j < 18; j++) { if ((1 << j) & k) { ret = max(ret, mx[j][v]); v = dp[j][v]; } } return make_pair(v, ret); } pair<int, int> Lca(int u, int v) { if (dep[u] > dep[v]) swap(u, v); int ret = 0; tie(v, ret) = kth(v, dep[v] - dep[u]); for (int j = 17; j >= 0; j--) { if (dp[j][v] != dp[j][u]) { ret = max({ret, mx[j][u], mx[j][v]}); v = dp[j][v], u = dp[j][u]; } } if (u == v) return make_pair(u, ret); else return make_pair(dp[0][u], max({ret, mx[0][u], mx[0][v]})); } void dfs(int v, int par) { dep[v] = dep[par] + 1; for (auto [u, w]: adj[v]) { if (u == par) continue; mx[0][u] = w; dp[0][u] = v; for (int j = 1; j < 18; j++) { mx[j][u] = max(mx[j - 1][u], mx[j - 1][dp[j - 1][u]]); dp[j][u] = dp[j - 1][dp[j - 1][u]]; } dfs(u, v); } } void init(int N2, int M, vector<int> U, vector<int> V, vector<int> W) { n = N2, m = M; vector<tuple<int, int, int>> se2; for (int i = 0; i < m; i++) { auto [u, v, w] = make_tuple(U[i] + 1, V[i] + 1, W[i]); se2.push_back({w, u, v}); } vector<vector<int>> nodes(n + 1); for (int i = 1; i <= n; i++) { nodes[i].push_back(i); } sort(se2.begin(), se2.end()); vector<int> par(n + 1, -1); function<int(int)> getpar = [&](int x) { return (par[x] < 0 ? x : getpar(par[x])); }; auto mrg = [&](int x, int y, int w) { x = getpar(x), y = getpar(y); if (x == y) { if (dis2[x] > w) { for (int u: nodes[x]) { dis2[u] = w; } } return 0; } if (par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; if (dis2[y] != INT_MAX && dis2[x] == INT_MAX) { for (int u: nodes[x]) { dis2[u] = w; } } if (dis2[y] == INT_MAX && dis2[x] != INT_MAX) { for (int u: nodes[y]) { dis2[u] = w; } } for (int u: nodes[y]) { nodes[x].push_back(u); } nodes[y].clear(); return 1; }; for (int i = 1; i <= n; i++) { dis2[i] = INT_MAX; } for (auto [w, u, v]: se2) { if (mrg(u, v, w)) { adj[u].push_back({v, w}), adj[v].push_back({u, w}); } } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> se; for (int i = 1; i <= n; i++) { sort(adj[i].begin(), adj[i].end(), [&](pair<int, int> a, pair<int, int> b) { return a.second < b.second; }); } for (int i = 1; i <= n; i++) { if ((int)adj[i].size() > 2) { dis[i] = adj[i][2].second; se.push({dis[i], i}); } else dis[i] = INT_MAX; } while (!se.empty()) { auto [ds, v] = se.top(); se.pop(); if (ds != dis[v]) continue; for (auto [u, w]: adj[v]) { if (dis[u] > max(dis[v], w)) { dis[u] = max(dis[v], w); se.push({dis[u], u}); } } } dfs(1, 0); for (int i = 1; i <= n; i++) { dis[i] = min(dis[i], dis2[i]); } } int getMinimumFuelCapacity(int X, int Y) { auto [u, v] = make_tuple(X + 1, Y + 1); if (dis[u] == INT_MAX) return -1; return max(Lca(u, v).second, min(dis[u], dis[v])); }
#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...