#include "swap.h"
#include <bits/stdc++.h>
#define FOR(i,x,n) for(int i=x; i<n; i++)
#define F0R(i,n) FOR(i,0,n)
#define ROF(i,x,n) for(int i=n-1; i>=x; i--)
#define R0F(i,n) ROF(i,0,n)
#define WTF cout << "WTF" << endl
#define IOS ios::sync_with_stdio(false); cin.tie(0)
#define F first
#define S second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
const int N = 3e5 + 7;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;
struct Edge {
int sp, ep, val;
inline bool operator < (const Edge &other) {
return val < other.val;
}
} eset[N];
int n, m;
int par[N], weight[N], height[N];
int deg[N], ans[N], up[N][LOG];
bool possible[N];
VI adj[N];
int grand(int x) {
if (par[x] < 0) return x;
return par[x] = grand(par[x]);
}
inline void merge(int a, int b, int x) {
deg[a]++; deg[b]++;
if (deg[a] >= 3 || deg[b] >= 3) possible[n] = 1;
a = grand(a); b = grand(b);
possible[n] |= possible[a] | possible[b];
adj[n].pb(a);
if (a != b) adj[n].pb(b);
else possible[n] = 1;
weight[n] = x;
par[a] = par[b] = n;
n++;
return;
}
void dfs(int now = n - 1, int best = INF, int h = 0) {
if (possible[now]) best = weight[now];
ans[now] = best;
height[now] = h;
for(int on : adj[now]) {
dfs(on, best, h + 1);
up[on][0] = now;
}
return;
}
void precalc() {
up[n - 1][0] = up[n][0] = 0;
FOR(k, 1, LOG) F0R(i, n + 1)
up[i][k] = up[ up[i][k - 1] ][k - 1];
return;
}
inline int lca(int a, int b) {
if (height[a] < height[b]) swap(a, b);
R0F(i, LOG) if (height[a] - (1 << i) >= height[b])
a = up[a][i];
if (a == b) return a;
R0F(i, LOG) if (up[a][i] != up[b][i]) {
a = up[a][i];
b = up[b][i];
}
return up[a][0];
}
void init(int p, int q, VI us, VI vs, VI ws) {
n = p; m = q;
F0R(i, m) {
eset[i].sp = us[i];
eset[i].ep = vs[i];
eset[i].val = ws[i];
}
fill(par, par + N, -1);
sort(eset, eset + m);
F0R(i, m) merge(eset[i].sp, eset[i].ep, eset[i].val);
dfs();
precalc();
}
int getMinimumFuelCapacity(int x, int y) {
int z = lca(x, y);
return (ans[z] == INF ? -1 : ans[z]);
}
/*int main() {
int s, t;
cin >> s >> t;
VI a(t), b(t), c(t);
F0R(i, t) cin >> a[i] >> b[i] >> c[i];
init(s, t, a, b, c);
int q; cin >> q;
while(q--) {
int l, r; cin >> l >> r;
getMinimumFuelCapacity(l, r);
}
}
Compilation message
swap.cpp:131:1: error: unterminated comment
131 | /*int main() {
| ^
