//#include "swap.h"
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////////////
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
vector<array<int, 3> > edges(MAXN * 2);
int DP[20][MAXN * 3];
struct ufds {
bool isLine;
pair<int, int> endpoints;
int parent, value, depth;
ufds(int x) {
isLine = true;
endpoints = {x, x};
parent = x;
value = 1e9;
depth = 0;
}
} *Node[MAXN * 3];
int Find(int x) {
if(Node[x]->parent == x) {
return x;
}
return Node[x]->parent = Find(Node[x]->parent);
}
void Unite(int a, int b, int new_idx, int cur_val) {
int original_a = a, original_b = b;
a = Find(a);
b = Find(b);
Node[a]->parent = new_idx;
Node[b]->parent = new_idx;
Node[new_idx]->value = cur_val;
DP[0][a] = new_idx;
DP[0][b] = new_idx;
if(a == b || !Node[a]->isLine || !Node[b]->isLine) {
Node[new_idx]->isLine = false;
Node[new_idx]->endpoints = {-1, -1};
}
else {
//cout << "a = " << a << ", b = " << b << "\n";
//cout << "A Line = " << Node[a]->endpoints.first << ", " << Node[a]->endpoints.second << "\n";
//cout << "B Line = " << Node[b]->endpoints.first << ", " << Node[b]->endpoints.second << "\n";
if(Node[a]->endpoints.first != original_a) {
swap(Node[a]->endpoints.first, Node[a]->endpoints.second);
}
if(Node[b]->endpoints.first != original_b) {
swap(Node[b]->endpoints.first, Node[b]->endpoints.second);
}
if(original_a == Node[a]->endpoints.first && original_b == Node[b]->endpoints.first) {
Node[new_idx]->isLine = true;
Node[new_idx]->endpoints = {Node[a]->endpoints.second, Node[b]->endpoints.second};
}
else {
Node[new_idx]->isLine = false;
Node[new_idx]->endpoints = {-1, -1};
}
}
}
bool cmp(array<int, 3> a, array<int, 3> b) {
return a[2] < b[2];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
for(int i = 0; i < 20; i++) {
for(int j = 0; j < MAXN * 3; j++) {
DP[i][j] = -1;
}
}
for(int i = 0; i < M; i++) {
edges[i] = {U[i], V[i], W[i]};
}
sort(edges.begin(), edges.begin() + M, cmp);
int cur_new = N;
for(int i = 0; i < MAXN * 3; i++) {
Node[i] = new ufds(i);
}
for(int i = 0; i < M; i++) {
//cout << Find(edges[i][0]) << " " << Find(edges[i][1]) << "\n";
int x = Find(edges[i][0]), y = Find(edges[i][1]);
//cout << "x = " << x << ", Node[x] is a line? " << Node[x]->isLine << "\n";
if(x != y || Node[x]->isLine == true) {
//cout << "Uniting edge: (" << edges[i][0] << ", " << edges[i][1] << ", " << edges[i][2] << ")\n";
Unite(edges[i][0], edges[i][1], cur_new++, edges[i][2]);
}
}
assert(cur_new <= MAXN * 3);
for(int i = 1; i < 20; i++) {
for(int j = 0; j < cur_new; j++) {
if(DP[i - 1][j] != -1) {
DP[i][j] = DP[i - 1][DP[i - 1][j]];
}
else {
DP[i][j] = -1;
}
}
}
}
bool Check(int val, int X, int Y) {
for(int i = 19; i >= 0; i--) {
if(DP[i][X] != -1 && Node[DP[i][X]]->value <= val) {
X = DP[i][X];
}
if(DP[i][Y] != -1 && Node[DP[i][Y]]->value <= val) {
Y = DP[i][Y];
}
}
return (X == Y && Node[X]->isLine == false);
}
int getMinimumFuelCapacity(int X, int Y) {
int ans = 1e9 + 2;
int l = 0, r = 1e9;
while(l <= r) {
int mid = (l + r) / 2;
if(Check(mid, X, Y)) {
r = mid - 1;
ans = mid;
}
else {
l = mid + 1;
}
}
if(ans == 1e9 + 2) {
ans = -1;
}
return ans;
}
/////////////////////////////////////////////////////////////////////////////////////////////////
int main() {
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> U(M), V(M), W(M);
for (int i = 0; i < M; ++i) {
assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
}
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> X(Q), Y(Q);
for (int i = 0; i < Q; ++i) {
assert(2 == scanf("%d %d", &X[i], &Y[i]));
}
init(N, M, U, V, W);
std::vector<int> minimum_fuel_capacities(Q);
for (int i = 0; i < Q; ++i) {
minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
}
for (int i = 0; i < Q; ++i) {
printf("%d\n", minimum_fuel_capacities[i]);
}
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccpnT78d.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccyYShSg.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
