#include "swap.h"
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
//
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
vector<int>adj[500005];
int cost[500005];
struct DSU{
vector<int>e;
void init(int n){
e=vector<int>(n,-1);
}
int get(int x){return e[x]<0?x:e[x]=get(e[x]);}
bool unite(int x, int y){ //x is par
x=get(x),y=get(y);
if(x==y) return 0;
adj[x].push_back(y);
adj[y].push_back(x);
e[x]+=e[y];
e[y]=x;
return 1;
}
};
int two[22][500005];
int d[500005];
void dfs(int index, int par){
for(int x=0;x<20;x++){
if(two[x][index]==-1) break;
two[x+1][index]=two[x][two[x][index]];
}
for(auto it:adj[index]){
if(it==par) continue;
two[0][it]=index;
d[it]=d[index]+1;
dfs(it,index);
}
}
int lca(int a, int b){
if(d[a]>d[b]) swap(a,b);
int diff=d[b]-d[a];
for(int x=0;x<20;x++){
if(diff&(1<<x)) b=two[x][b];
}
if(a==b) return a;
for(int x=19;x>=0;x--){
if(two[x][b]!=two[x][a]){
a=two[x][a];
b=two[x][b];
}
}
return two[0][a];
}
bool done[300005];
int root=0;
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
pair<int,pii>edge[m];
for(int x=0;x<m;x++){
edge[x].first=w[x];
edge[x].second={u[x],v[x]};
}
sort(edge,edge+m);
DSU dsu;
dsu.init(n+m+20);
int in[n+5];
memset(in,0,sizeof(in));
for(int x=0;x<m;x++){
int l=edge[x].second.first;
int r=edge[x].second.second;
int hold=edge[x].first;
in[l]++;
in[r]++;
if(in[l]>2||in[r]>2) done[n+x+1]=true;
l=dsu.get(l);
r=dsu.get(r);
if(l==r||done[l]||done[r]) done[n+x+1]=true;
dsu.unite(n+x+1,l);
dsu.unite(n+x+1,r);
cost[n+x+1]=hold;
}
memset(two,-1,sizeof(two));
dfs(n+m,-1);
root=n+m;
}
int getMinimumFuelCapacity(int x, int y){
int hold=lca(x,y);
show(hold,hold);
if(done[hold]){
return cost[hold];
}
int cur=hold;
for(int bit=19;bit>=0;bit--){
if(d[hold]&(1<<bit)){
if(!done[two[bit][cur]]){
cur=two[bit][cur];
}
}
}
show(cur,cur);
if(m<=2) assert(cur==root);
if(cur==root) return -1;
return cost[two[0][cur]];
}
//
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
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:130:5: error: 'm' was not declared in this scope
130 | if(m<=2) assert(cur==root);
| ^
