#include <bits/stdc++.h>
using namespace std;
//#include "swap.h"
const int LOGN = 19;
vector<int> dep, val;
vector<bool> lin;
vector<array<int, LOGN>> anc;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
vector<tuple<int, int, int>> E(M);
for (int i = 0; i < M; i++)
E[i] = {U[i], V[i], W[i]};
sort(E.begin(), E.end(),
[](const auto &a, const auto &b) {
return get<2>(a) < get<2>(b);
}
);
struct node {
int par, val; bool lin;
node() = default;
node(int _par, int _val, bool _lin) : par(_par), val(_val), lin(_lin) {}
};
vector<node> T; T.reserve(N + M);
vector<bool> ep(N);
vector<int> rt(N);
for (int i = 0; i < N; i++) {
T.emplace_back(i, 0, true);
ep[i] = true;
rt[i] = i;
}
for (auto [u, v, w] : E) {
while (rt[u] != T[rt[u]].par)
rt[u] = T[rt[u]].par;
int up = rt[u];
while (rt[v] != T[rt[v]].par)
rt[v] = T[rt[v]].par;
int vp = rt[v];
int c = T.size();
if (up != vp) {
if (T[up].lin && T[vp].lin && ep[u] && ep[v]) {
T[up].par = T[vp].par = c;
T.emplace_back(c, w, true);
if (up != u)
ep[u] = false;
if (vp != v)
ep[v] = false;
} else {
T[up].par = T[vp].par = T.size();
T.emplace_back(c, w, false);
}
} else if (T[up].lin) {
T[up].par = c;
T.emplace_back(c, w, false);
}
/*
cout << "edge " << u << ' ' << v << ' ' << w << '\n';
for (int i = 0; i < T.size(); i++)
cout << i << " : " << T[i].par << ' ' << T[i].val << ' ' << (T[i].lin ? "line" : "not line") << '\n';
cout << '\n';
*/
}
int S = T.size();
anc.resize(S);
dep.resize(S);
val.resize(S);
lin.resize(S);
vector<vector<int>> tree(S);
for (int i = 0; i < S; i++) {
anc[i][0] = T[i].par;
val[i] = T[i].val;
lin[i] = T[i].lin;
if (i != T[i].par)
tree[T[i].par].push_back(i);
}
for (int k = 1; k < LOGN; k++)
for (int i = 0; i < S; i++)
anc[i][k] = anc[anc[i][k - 1]][k - 1];
const auto dfs = [&](const auto &self, int u) -> void {
for (int v : tree[u]) {
dep[v] = dep[u] + 1;
self(self, v);
}
};
for (int i = 0; i < S; i++)
if (i == T[i].par) {
dep[i] = 0;
dfs(dfs, i);
}
}
int getMinimumFuelCapacity(int u, int v) {
if (dep[u] > dep[v])
swap(u, v);
for (int k = LOGN - 1; k >= 0; k--)
if ((dep[v] - dep[u]) >> k & 1)
v = anc[v][k];
//assert(dep[u] == dep[v]);
if (u != v) {
for (int k = LOGN - 1; k >= 0; k--)
if (anc[u][k] != anc[v][k])
u = anc[u][k], v = anc[v][k];
u = anc[u][0], v = anc[v][0];
if (u != v)
return -1;
}
if (!lin[u])
return val[u];
for (int k = LOGN - 1; k >= 0; k--)
if (lin[anc[u][k]])
u = anc[u][k];
u = anc[u][0];
if (lin[u]) {
return -1;
} else {
return val[u];
}
}
int main() {
int _N, _M;
cin >> _N >> _M;
vector<int> _U(_M), _V(_M), _W(_M);
for (int i = 0; i < _M; i++)
cin >> _U[i] >> _V[i] >> _W[i];
init(_N, _M, _U, _V, _W);
int _Q;
cin >> _Q;
while (_Q--) {
int _u, _v;
cin >> _u >> _v;
cout << getMinimumFuelCapacity(_u, _v) << '\n';
}
}
Compilation message
/usr/bin/ld: /tmp/cczCTEpJ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccgizr9M.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
