#include <bits/stdc++.h>
#include "swap.h"
#define ll long long
using namespace std;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 3e5 + 50;
int a[N];
struct dsu{
int curn = 0;
vector <int> sz, par, line, cost, st, en, degree;
vector < vector <int>> in, p, cc;
vector < vector <pair <int, int>>> ed;
int dfstimer = 1;
void prepare(int n) {
in.clear();
p.clear();
cc.clear();
for (int i = 0; i <= n; i++) {
ed[i].clear();
}
curn = n;
sz.assign(n + 1, 1);
par.assign(n + 1, 0);
line.assign(n + 1, 1);
cost.assign(n + 1, 1e9 + 10);
st.assign(n + 1, 0);
en.assign(n + 1, 0);
degree(n + 1, 0);
in.resize(n + 1);
ed.resize(n + 1);
for (int i = 0; i <= n; i++) {
in[i].pb(i);
p.pb(vector <int> (20, 0));
cc.pb(vector <int> (20, 0));
}
}
int get(int a) {
return par[a] ? get(par[a]) : a;
}
void dfs(int u, int v) {
st[u] = ++dfstimer;
p[u][0] = v;
for (int j = 1; j < 20; j++) {
p[u][j] = p[p[u][j - 1]][j - 1];
cc[u][j] = max(cc[u][j - 1], cc[p[u][j - 1]][j - 1]);
}
for (auto x : ed[u]) {
if (x.f == v)
continue;
cc[x.f][0] = x.s;
dfs(x.f, u);
}
en[u] = dfstimer;
}
bool is(int a, int b) {
return st[a] <= st[b] && en[a] >= st[b];
}
int lca(int a, int b) {
if (is(a, b))
return a;
if (is(b, a))
return b;
for (int j = 19; j >= 0; j--) {
if (is(p[a][j], b) == 0)
a = p[a][j];
}
return p[a][0];
}
int answer(int a, int b) {
int c = lca(a, b), ans = max(cost[a], cost[b]);
for (int j = 19; j >= 0; j--) {
if (p[a][j] != c && is(c, p[a][j])) {
ans = max(ans, cc[a][j]);
a = p[a][j];
}
if (p[b][j] != c && is(c, p[b][j])) {
ans = max(ans, cc[b][j]);
b = p[b][j];
}
}
return ans;
}
void unite(int a, int b, int w) {
degree[a]++;
degree[b]++;
int mx = max(degree[a], degree[b]);
a = get(a), b = get(b);
if (a == b) {
line[a] = 0;
for (auto x : in[a]) {
cost[x] = w;
}
in[a].clear();
return;
}
ed[a].pb({b, w});
ed[b].pb({a, w});
if (sz[a] < sz[b])
swap(a, b);
par[b] = a;
line[a] = line[a] & line[b];
if (mx > 2) {
line[a] = 0;
}
for (auto x : in[b])
in[a].pb(x);
if (line[a] == 0) {
for (auto x : in[a]) {
cost[x] = w;
}
in[a].clear();
}
}
} D;
void init(int n, int m, vector <int> u, vector <int> v, vector <int> w) {
D.prepare(n);
vector < vector <int>> edge;
for (int i = 0; i < m; i++) {
edge.pb({w[i], u[i] + 1, v[i] + 1});
}
sort(all(edge));
for (auto x : edge) {
D.unite(x[1], x[2], x[0]);
}
D.dfs(1, 1);
}
int getMinimumFuelCapacity(int a, int b) {
a++;
b++;
int ans = D.answer(a, b);
if (ans > 1e9)
return -1;
return ans;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
--------------------------------------------------|
3 2
0 1 5
0 2 5
1
1 2
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
3
10
4
--------------------------------------------------|
-1
--------------------------------------------------|
==================================================+
*/
Compilation message
swap.cpp: In member function 'void dsu::prepare(int)':
swap.cpp:49:24: error: no match for call to '(std::vector<int>) (int, int)'
49 | degree(n + 1, 0);
| ^
