#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e6 + 2, LG = 20, inf = 1e18;
int n, m, pu, pv, u[maxn], v[maxn], w[maxn], d[maxn], par[maxn], id[maxn], deg[maxn], st[LG][maxn], res[maxn];
bool good[maxn];
vector<int> adj[maxn];
bool cmp (int x, int y)
{
return w[x] < w[y];
}
int find_set (int u)
{
if (par[u] < 0) return u;
return (par[u] = find_set(par[u]));
}
void union_set (int i)
{
deg[u[id[i]]]++; deg[v[id[i]]]++;
pu = find_set(u[id[i]]); pv = find_set(v[id[i]]);
if (pu == pv)
{
par[n + i] += par[pu];
par[pu] = n + i;
adj[n + i].push_back(pu);
good[n + i] = true;
}
else
{
par[n + i] += par[pu];
par[n + i] += par[pv];
par[pu] = par[pv] = n + i;
adj[n + i].push_back(pu);
adj[n + i].push_back(pv);
if (deg[u[id[i]]] > 2 || deg[v[id[i]]] > 2 || good[pu] || good[pv]) good[n + i] = true;
}
}
void dfs (int u, int p)
{
st[0][u] = p;
if (good[u]) res[u] = w[id[u - n]];
else res[u] = res[p];
for (int v : adj[u])
{
d[v] = d[u] + 1;
dfs(v, u);
}
}
int lca (int u, int v)
{
if (d[u] < d[v]) swap(u, v);
int diff = d[u] - d[v];
for (int j = LG - 1; j >= 0; j--)
if ((diff >> j) & 1)
{
diff ^= (1 << j);
u = st[j][u];
}
if (u == v) return u;
for (int j = LG - 1; j >= 0; j--)
if (st[j][u] != st[j][v])
{
u = st[j][u];
v = st[j][v];
}
return st[0][u];
}
void init (int N, int M, int* U, int* V, int* W)
{
n = N; m = M;
for (int i = 1; i <= n; i++) par[i] = -1;
for (int i = m; i >= 1; i--)
{
u[i] = U[i - 1] + 1;
v[i] = V[i - 1] + 1;
w[i] = W[i - 1];
id[i] = i;
}
sort(id + 1, id + m + 1, cmp);
for (int i = 1; i <= m; i++) union_set(i);
res[0] = -1;
dfs(n + m, 0);
for (int j = 1; j < LG; j++)
for (int i = 1; i <= n + m; i++)
st[j][i] = st[j - 1][st[j - 1][i]];
}
int getMinimumFuelCapacity (int X, int Y)
{
X++; Y++;
return res[lca(X, Y)];
}
#ifdef rtgsp
int main() {
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
int N, M, Q;
cin >> N >> M >> Q;
int U[M], V[M], W[M];
for (int i = 0; i < M; i++) cin >> U[i];
for (int i = 0; i < M; i++) cin >> V[i];
for (int i = 0; i < M; i++) cin >> W[i];
init(N, M, U, V, W);
while (Q--)
{
int X, Y;
cin >> X >> Y;
cout << getMinimumFuelCapacity(X, Y) << '\n';
}
}
#endif
Compilation message
/usr/bin/ld: /tmp/cctJQ0gX.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
