#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
int lab[N], order[N], deg[N], noline[N], mx[N], h[N];
int par[20][N], f[20][N];
int cur;
vector<int> lst[N];
vector<pair<int, int> > adj[N];
int root(int v) {
return lab[v] < 0 ? v : lab[v] = root(lab[v]);
}
void update(int u) {
if (mx[u] <= 2) return;
for(int j : lst[u]) noline[j] = cur;
lst[u].clear();
}
bool join(int u, int v) {
u = root(u); v = root(v);
if (u == v) return 0;
if (lab[u] > lab[v]) swap(u, v);
mx[u] = max(mx[u], mx[v]);
lab[u] += lab[v];
for(int j : lst[v]) lst[u].push_back(j);
lab[v] = u;
return 1;
}
void dfs(int u) {
for(auto [v, w] : adj[u]) if (v != par[0][u]) {
par[0][v] = u;
f[0][v] = w;
for(int j = 1; j <= 17; j++) {
int p = par[j - 1][v];
par[j][v] = par[j - 1][p];
f[j][v] = max(f[j - 1][v], f[j - 1][p]);
}
h[v] = h[u] + 1;
dfs(v);
}
}
int lca(int u, int v) {
int ret = 0;
if (h[u] < h[v]) swap(u, v);
int delta = h[u] - h[v];
for(int j = 0; j <= 17; j++) if ((delta >> j) & 1) {
ret = max(ret, f[j][u]);
u = par[j][u];
}
if (u == v) return ret;
for(int j = 17; j >= 0; j--) if (par[j][u] != par[j][v]) {
ret = max(ret, f[j][u]);
ret = max(ret, f[j][v]);
u = par[j][u];
v = par[j][v];
}
return max({ret, f[0][u], f[0][v]});
}
void init(int n, int m, int u[], int v[], int w[]) {
for(int i = 0; i < n; i++) {
lab[i] = -1;
lst[i].push_back(i);
}
for(int i = 0; i < m; i++) order[i] = i;
sort(order, order + m, [&] (int &x, int &y) {
return w[x] < w[y];
});
for(int j = 0; j < m; j++) {
int i = order[j];
cur = w[i];
if (join(u[i], v[i])) {
adj[u[i]].push_back({v[i], w[i]});
adj[v[i]].push_back({u[i], w[i]});
}
else mx[root(u[i])] = 3;
int r = root(u[i]);
mx[r] = max(mx[r], max(++deg[u[i]], ++deg[v[i]]));
update(r);
}
dfs(0);
}
int getMinimumFuelCapacity(int x, int y) {
if (!noline[x]) return -1;
return max(noline[x], lca(x, y));
}
//int main() {
// #define task ""
// cin.tie(0) -> sync_with_stdio(0);
// if (fopen ("task.inp", "r")) {
// freopen ("task.inp", "r", stdin);
// freopen ("task.out", "w", stdout);
// }
// if (fopen (task".inp", "r")) {
// freopen (task".inp", "r", stdin);
// freopen (task".out", "w", stdout);
// }
//// int u[1000] = {0, 0, 1, 1, 1, 2};
//// int v[1000] = {1, 2, 2, 3, 4, 3};
//// int w[1000] = {4, 4, 1, 2, 10, 3};
// int u[200] = {0, 0};
// int v[200] = {1, 2};
// int w[200] = {5, 5};
// init(3, 2, u, v, w);
// cout << getMinimumFuelCapacity(1, 2);
//}
Compilation message
/usr/bin/ld: /tmp/ccrkfDIN.o: in function `main':
grader.cpp:(.text.startup+0x1c3): undefined reference to `init(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
