| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 961421 | kilkuwu | Swapping Cities (APIO20_swap) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
// we need to find first cycle and first three;
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) {
adj[u].emplace_back(w, v);
adj[v].emplace_back(w, u);
auto pu = find(u), pv = find(v);
if (adj[u].size() > 2 || adj[v].size() > 2) {
ckmin(par[num_nodes].second, w);
}
if (pu == pv) {
ckmin(par[num_nodes].second, w);
}
par[pu.first] = par[pv.first] = num_nodes;
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;
}
#ifdef LOCAL
#endif