#include <bits/stdc++.h>
//#define int long long
//#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e5 + 5;
const int oo = 2e9;
//const int mod = 1e9 + 7;
struct e{
int u, v, w;
} p[N];
bool comp(e g1, e g2){
return g1.w < g2.w;
}
int n, m, d[N], in[2][N], out[2][N], dp[2][N][22], mx[2][N][22], demin[2], demout[2], root, pa[N], sz[N], f[N], deg[N];
vector<pii> g[2][N];
int fin(int u){
return pa[u] == u ? u : fin(pa[u]);
}
void dfs(int t,int u,int v,int ts){
in[t][u] = ++demin[t];
if(u == root) for(int i = 0; i <= 20; i ++) dp[t][u][i] = u;
else{
dp[t][u][0] = v;
mx[t][u][0] = ts;
for(int i = 1; i <= 20; i ++){
dp[t][u][i] = dp[t][dp[t][u][i - 1]][i - 1];
mx[t][u][i] = max(mx[t][u][i - 1], mx[t][dp[t][u][i - 1]][i - 1]);
}
}
for(auto jj : g[t][u]){
int j = jj.fi;
int w = jj.se;
if(j == v) continue;
if(t == 0) f[j] = min(f[j], max(f[u], w));
dfs(t, j, u, w);
}
out[t][u] = ++demout[t];
}
bool kt(int t,int u,int v){
return in[t][u] <= in[t][v] && out[t][u] >= out[t][v];
}
int lca(int t,int u,int v){
if(kt(t, u, v)) return u;
else{
int kq = u;
for(int i = 20; i >= 0; i --){
if(kt(t, dp[t][u][i], v)) kq = dp[t][u][i];
else u = dp[t][u][i];
}
return kq;
}
}
int get(int u,int v){
int ret = 0, k = lca(1, u, v), tmp = u;
for(int i = 20; i >= 0; i --){
if(!kt(1, dp[1][u][i], v) || dp[1][u][i] == k){
ret = max(ret, mx[1][u][i]);
u = dp[1][u][i];
}
}
u = tmp;
for(int i = 20; i >= 0; i --){
if(!kt(1, dp[1][v][i], u) || dp[1][v][i] == k){
ret = max(ret, mx[1][v][i]);
v = dp[1][v][i];
}
}
return ret;
}
void dsu(int x,int y,int w){
int u = x, v = y;
x = fin(x);
y = fin(y);
if(x == y){
f[x] = min(f[x], w);
cerr << u << " " << v << " " << x << " " << f[x] << "change\n";
return;
}
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
pa[y] = x;
cerr << x << " " << y << " " << w << " f\n";
g[0][x].push_back({y, w});
g[1][u].pb({v, w});
g[1][v].pb({u, w});
f[x] = min(f[x], max(w, f[y]));
d[x] = max(d[x], d[y]);
// re[x] = max({re[x], re[y], w});
}
void init(int N,int M, vector<int> U, vector<int> V, vector<int> W){
n = N;
m = M;
for(int i = 1; i <= n; i ++){
f[i] = oo;
pa[i] = i;
sz[i] = 1;
}
for(int i = 0; i < m; i ++){
p[i + 1].u = U[i] + 1;
p[i + 1].v = V[i] + 1;
p[i + 1].w = W[i];
}
sort(p + 1, p + m + 1, comp);
for(int i = 1; i <= m; i ++){
if(p[i].u == p[i].v) continue;
dsu(p[i].u, p[i].v, p[i].w);
int u = p[i].u, v = p[i].v, w = p[i].w;
deg[u]++;
deg[v]++;
int j = fin(u);
d[j] = max({d[j], deg[u], deg[v]});
if(d[j] >= 3) f[j] = min(f[j], w);
cerr << u << " " << v << " " << w << " " << j << " " << f[j] << " gggg\n";
}
root = fin(1);
// cerr << root << " g\n";
dfs(0, root, 0, 0);
dfs(1, root, 0, 0);
}
int getMinimumFuelCapacity(int x,int y){
x++;
y++;
int t = lca(0, x, y), kq = max(f[t], get(x, y));
// cerr << x << " " << y << " " << t << " " << f[t] << " " << get(x, y) << "f\n";
if(f[t] == (int)oo) return -1;
return kq;
}
#define LOCAL
#ifdef LOCAL
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
cin >> n >> m;
vector<int> u, v, w;
for(int i = 1; i <= m; i ++){
int x, y, t; cin >> x >> y >> t;
u.pb(x - 1);
v.pb(y - 1);
w.pb(t);
}
init(n, m, u, v, w);
int rq = 0;
cin >> rq;
// cerr << rq << "fifai\n";
while(rq--){
int x, y;
cin >> x >> y;
// cerr << x << " " << y << " rr\n";
x--;
y--;
cout << getMinimumFuelCapacity(x, y) << "\n";
}
}
#endif // LOCAL
Compilation message
swap.cpp: In function 'int main()':
swap.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | freopen(task ".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
swap.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
159 | freopen(task ".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccgKWiRM.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc0ELNMM.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
