#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) {
//auto start = chrono::high_resolution_clock::now();
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, com; bool lin;
node() = default;
node(int _par, int _val, int _com, bool _lin) : par(_par), val(_val), com(_com), lin(_lin) {}
};
vector<node> T;
T.reserve(N + M);
vector<bool> ep(N);
for (int i = 0; i < N; i++) {
T.emplace_back(i, 0, i, true);
ep[i] = true;
}
const auto find_com = [&](const auto &self, int u) -> int {
if (u == T[u].com)
return u;
return T[u].com = self(self, T[u].com);
};
for (auto [u, v, w] : E) {
int up = find_com(find_com, u), vp = find_com(find_com, 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[up].com = T[vp].com = c;
T.emplace_back(c, w, c, true);
if (up != u)
ep[u] = false;
if (vp != v)
ep[v] = false;
} else {
T[up].par = T[vp].par = c;
T[up].com = T[vp].com = c;
T.emplace_back(c, w, c, false);
}
} else if (T[up].lin) {
T[up].par = c;
T[up].com = c;
T.emplace_back(c, w, c, 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';
*/
}
//auto stop1 = chrono::high_resolution_clock::now();
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);
}
//auto stop2 = chrono::high_resolution_clock::now();
//cout << "duration of 1 = " << duration_cast<chrono::microseconds>(stop1 - start).count() << '\n';
//cout << "duration of 2 = " << duration_cast<chrono::microseconds>(stop2 - stop1).count() << '\n';
//cout << "jumps = " << jumps << '\n';
}
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() {
//freopen("data.txt", "r", stdin);
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/ccyyKDKM.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccKBR7GJ.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
