//happier ending for folks like us?
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 15;
const int M = 2e5 + 5;
const int L = 21;
int p[N], dpr[N], pr[N][L], ext[N], P[N], h[N], rt, D[N], deg[N];
vector<int> adj[N], Wtmp;
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]);
}
}
void add_edge(int u, int e) {
adj[e].push_back(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] = id + M;
dpr[v] = id + M;
D[id + M] = max({D[u], D[v], deg[tu], deg[tv]});
add_edge(u, id + M);
add_edge(v, id + M);
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, 0x3f3f3f, 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 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])];
assert(Y != X);
for (int i = L - 1; i >= 0; i--) if (pr[Y][i] != pr[X][i])
Y = pr[Y][i], X = pr[X][i];
assert(pr[X][0] == pr[Y][0]);
assert(lca >= M);
int lca = pr[X][0], l = lca - M, w = Wtmp[l];
if (D[lca] > 2) return w;
w = max(w, ext[lca]);
return w > M ? -1 : w;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from swap.cpp:3:
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:70:9: error: 'lca' was not declared in this scope
70 | assert(lca >= M);
| ^~~
swap.cpp:72:25: error: 'w' was not declared in this scope
72 | if (D[lca] > 2) return w;
| ^
swap.cpp:73:2: error: 'w' was not declared in this scope
73 | w = max(w, ext[lca]);
| ^
swap.cpp:71:22: warning: unused variable 'l' [-Wunused-variable]
71 | int lca = pr[X][0], l = lca - M, w = Wtmp[l];
| ^
