| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1320597 | vinayakagrawal | Swapping Cities (APIO20_swap) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int LOG = 17;
vector<pair<int,int>> mst[MAXN];
int up[MAXN][LOG];
int mx[MAXN][LOG];
int depth[MAXN];
int parent[MAXN];
struct Edge {
int u, v, w;
};
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void dfs(int v, int p, int w) {
up[v][0] = p;
mx[v][0] = w;
for (int i = 1; i < LOG; i++) {
up[v][i] = up[ up[v][i-1] ][i-1];
mx[v][i] = max(mx[v][i-1], mx[ up[v][i-1] ][i-1]);
}
for (auto [to, wt] : mst[v]) {
if (to == p) continue;
depth[to] = depth[v] + 1;
dfs(to, v, wt);
}
}
int query(int u, int v) {
int ans = 0;
if (depth[u] < depth[v]) swap(u, v);
// lift u up
for (int i = LOG-1; i >= 0; i--) {
if (depth[u] - (1 << i) >= depth[v]) {
ans = max(ans, mx[u][i]);
u = up[u][i];
}
}
if (u == v) return ans;
// lift both
for (int i = LOG-1; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
ans = max(ans, mx[u][i]);
ans = max(ans, mx[v][i]);
u = up[u][i];
v = up[v][i];
}
}
// last step to LCA
ans = max(ans, mx[u][0]);
ans = max(ans, mx[v][0]);
return ans;
}
int main() {
int n, m, q;
cin >> n >> m >> q;
vector<Edge> edges(m);
for (int i = 0; i < m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
edges[i].u--;
edges[i].v--;
}
// DSU init
for (int i = 0; i < n; i++) parent[i] = i;
sort(edges.begin(), edges.end(), [](Edge &a, Edge &b) {
return a.w < b.w;
});
// build MST
for (auto &e : edges) {
int a = find(e.u);
int b = find(e.v);
if (a != b) {
parent[a] = b;
mst[e.u].push_back({e.v, e.w});
mst[e.v].push_back({e.u, e.w});
}
}
// preprocess LCA
dfs(0, 0, 0);
while (q--) {
int u, v;
cin >> u >> v;
u--; v--;
cout << query(u, v) << "\n";
}
}