#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define F first
#define S second
#define pb push_back
const int O = 3e5 + 5;
const int LOG = 25;
const int MOD = 1e9 + 7;
const ll inf = 1e9 + 5;
int n, m, q, par[O];
int deg[O];
int mn1[O], mn2[O];
int h[O], pr[LOG][O];
vector <int> g[O];
struct edge{
int u = 0, v = 0, w = 0, id = 0;
} e[O];
inline bool cmp(edge e1, edge e2){
return make_pair(e1.w, e1.id) < make_pair(e2.w, e2.id);
}
inline void clear(){
for (int v = 1; v < O; v ++){
par[v] = v;
mn1[v] = mn2[v] = inf;
}
return;
}
int find_par(int v){
if (par[v] == v) return v;
return par[v] = find_par(par[v]);
}
inline void merge(int u, int v, int w){
deg[u] ++; deg[v] ++;
int pu = find_par(u);
int pv = find_par(v);
if (pu == pv){
mn2[pv] = min(mn2[pv], w);
}
else {
n ++;
mn1[n] = w;
mn2[n] = min(mn2[pu], mn2[pv]);
par[pu] = par[pv] = n;
g[n].pb(pu); g[n].pb(pv);
pr[0][pu] = pr[0][pv] = n;
if (3 <= deg[u] || 3 <= deg[v]){
mn2[n] = min(mn2[n], w);
}
}
return;
}
void dfs(int v){
for (int u : g[v]){
h[u] = h[v] + 1;
dfs(u);
}
return;
}
void build(){
for (int i = 1; i < LOG; i ++){
for (int v = 1; v <= n; v ++){
pr[i][v] = pr[i - 1][pr[i - 1][v]];
}
}
return;
}
inline int get_par(int v, int dif){
for (int i = 0; i < LOG; i ++){
if ((dif >> i) & 1){
v = pr[i][v];
}
}
return v;
}
inline int LCA(int u, int v){
if (h[v] < h[u]) swap(u, v);
v = get_par(v, h[v] - h[u]);
if (u == v) return v;
for (int i = LOG - 1; i >= 0; i --){
if (pr[i][u] != pr[i][v]){
u = pr[i][u];
v = pr[i][v];
}
}
v = pr[0][v];
return v;
}
inline int getMinimumFuelCapacity(int X, int Y){
X ++; Y ++;
int lca = LCA(X, Y);
if (mn2[lca] != inf){
return max(mn1[lca], mn2[lca]);
}
for (int i = LOG - 1; i >= 0; i --){
int up = pr[i][lca];
if (up && mn2[up] == inf){
lca = up;
}
}
lca = pr[0][lca];
if (lca == 0) return -1;
return max(mn1[lca], mn2[lca]);
}
inline void init(int N, int M, int U[O], int V[O], int W[O]){
n = N; m = M;
for (int i = 0; i < m; i ++){
e[i].u = U[i] + 1;
e[i].v = V[i] + 1;
e[i].w = W[i];
e[i].id = i;
}
sort(e, e + M, cmp);
clear();
for (int i = 0; i < m; i ++){
merge(e[i].u, e[i].v, e[i].w);
}
dfs(n); build();
return;
}
Compilation message
/tmp/ccNsE8Aj.o: In function `main':
grader.cpp:(.text.startup+0x1a8): undefined reference to `init(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
grader.cpp:(.text.startup+0x214): undefined reference to `getMinimumFuelCapacity(int, int)'
collect2: error: ld returned 1 exit status
