/** Im the best because i work as hard as i possibly can **/
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl "\n"
const int N = 5e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 21;
struct edge
{
int v, u, c;
} E[N];
bool cmp(edge a, edge b) { return a.c < b.c; }
int ptr, D[N], par[N], ok[N], P[LOG][N], H[N], up[N];
vector < int > G[N];
int get(int x) { return (x == par[x]? x : par[x] = get(par[x])); }
void unify(int i)
{
++ ptr;
D[E[i].v] ++;
D[E[i].u] ++;
int v = get(E[i].v), u = get(E[i].u);
if(v == u)
{
ok[ptr] = 1;
G[ptr].push_back(v);
P[0][v] = par[v] = ptr;
return;
}
ok[ptr] = max({ok[v], ok[u], int(D[E[i].v] > 2), int(D[E[i].u] > 2)});
P[0][v] = P[0][u] = par[u] = par[v] = ptr;
G[ptr].push_back(v);
G[ptr].push_back(u);
}
void dfs(int v)
{
if(ok[v] == 0) up[v] = up[P[0][v]];
else up[v] = v;
H[v] = H[P[0][v]] + 1;
for(int T = 1; T < LOG; T ++)
P[T][v] = P[T - 1][P[T - 1][v]];
for(auto u : G[v])
dfs(u);
}
int LCA(int v, int u)
{
if(H[v] > H[u]) swap(u, v);
int del = (H[u] - H[v]);
for(int T = 0; T < LOG; T ++)
{
if(del >> T & 1)
{
u = P[T][u];
}
}
if(v == u) return v;
for(int T = LOG - 1; ~T; T --)
{
if(P[T][v] != P[T][u])
{
u = P[T][u];
v = P[T][v];
}
}
return P[0][v];
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W)
{
ptr = n;
for(int i = 1; i <= m; i ++)
{
E[i] = {V[i - 1], U[i - 1], W[i - 1]};
}
iota(par, par + N, 0);
sort(E + 1, E + m + 1, cmp);
for(int i = 1; i <= m; i ++)
{
unify(i);
}
dfs(ptr);
}
int getMinimumFuelCapacity(int u, int v)
{
int lca = LCA(u, v);
if(up[lca] == 0)
{
return -1;
}
return E[up[lca] - n].c;
}
/*
case 1:
5 6
1 2 4
1 3 4
3 4 3
4 2 2
2 5 10
2 3 1
3
2 3
3 5
1 2
case 2:
3 2
1 2 5
1 3 5
1
2 3
*/
Compilation message
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:114:24: error: 'n' was not declared in this scope
114 | return E[up[lca] - n].c;
| ^
