#include<bits/stdc++.h>
using namespace std;
#define LOCAL
#ifndef LOCAL
#include "swap.h"
#endif // LOCAL
const int N = 1e5 + 10;
int n, m;
vector<pair<int, int>> ad[N];
//tree
int f[N][17], g[N][17], dp[N][17], st[N], ed[N], it;
int dpin[N], dpout[N];
void dfs(int u, int pre = -1) {
st[u] = ++it;
for (int i = 1; i <= 16; ++i) {
f[u][i] = f[f[u][i - 1]][i - 1];
g[u][i] = max(g[u][i - 1], g[f[u][i - 1]][i - 1]);
dp[u][i] = min(dp[u][i - 1], dp[f[u][i - 1]][i - 1]);
}
vector<pair<int, int>> best;
sort(ad[u].begin(), ad[u].end(), [&] (auto& a, auto& b) {
return a.second < b.second;
});
for (auto duck : ad[u]) {
int v, w; tie(v, w) = duck;
if (v == pre) continue;
best.push_back({w, v});
}
sort(best.begin(), best.end());
dpin[u] = 1e9 + 1;
for (auto duck : ad[u]) {
int v, w; tie(v, w) = duck;
if (v == pre) continue;
f[v][0] = u;
g[v][0] = w;
if (best.size() >= 2) {
dp[v][0] = (best[0].second != v ? best[0].first : best[1].first);
} else dp[v][0] = 1e9 + 1;
dfs(v, u);
dpin[u] = min(dpin[u], max(w, dpin[v]));
}
if (best.size() >= 2) {
dpin[u] = min(dpin[u], best[1].first);
}
ed[u] = it;
}
void dfs_out(int u, int pre = 0) {
vector<pair<int, int>> best, bestmax;
for (auto duck : ad[u]) {
int v, w; tie(v, w) = duck;
best.push_back({w, v});
if (v == pre) continue;
bestmax.push_back({max(w, dpin[v]), v});
}
sort(best.begin(), best.end());
sort(bestmax.begin(), bestmax.end());
for (auto duck : ad[u]) {
int v, w; tie(v, w) = duck;
if (v == pre) continue;
dpout[v] = dpout[u];
if (bestmax.size() >= 2) {
dpout[v] = min(dpout[v], bestmax[0].second != v ? bestmax[0].first : bestmax[1].first);
}
if (best.size() >= 3) {
if (best[0].second != v && best[1].second != v) dpout[v] = min(dpout[v], best[1].first);
else dpout[v] = min(dpout[v], best[2].first);
}
dpout[v] = max(w, dpout[v]);
dfs_out(v, u);
}
}
bool anc(int u, int v) {
return st[u] <= st[v] && ed[u] >= ed[v];
}
int lca(int u, int v) {
if (anc(u, v)) return u;
if (anc(v, u)) return v;
for (int i = 16; i >= 0; --i)
if (!anc(f[u][i], v)) u = f[u][i];
return f[u][0];
}
int wmax(int u, int v) {
int ret = 0, l = lca(u, v);
for (int i = 16; i >= 0; --i) {
if (!anc(f[u][i], v) || f[u][i] == l) {
ret = max(ret, g[u][i]);
u = f[u][i];
}
}
for (int i = 16; i >= 0; --i) {
if (!anc(f[v][i], u) || f[v][i] == l) {
ret = max(ret, g[v][i]);
v = f[v][i];
}
}
return ret;
}
int binary_jump(int u, int v) {
int ret = 1e9 + 1;
for (int i = 16; i >= 0; --i) if (!anc(f[u][i], v)) {
ret = min(ret, dp[u][i]);
u = f[u][i];
}
for (int i = 16; i >= 0; --i) if (!anc(f[v][i], u)) {
ret = min(ret, dp[v][i]);
v = f[v][i];
}
return ret;
}
vector<int> co;
bool sub1;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n = N; m = M;
sub1 = 1;
for (int i = 0; i < m; ++i) {
int u = U[i], v = V[i], w = W[i];
co.push_back(w);
ad[u].push_back({v, w});
ad[v].push_back({u, w});
if (ad[u].size() > 2 || ad[v].size() > 2) sub1 = 0;
}
if (m == n - 1) {
dfs(0);
dpout[0] = 1e9 + 1;
dfs_out(0);
}
sort(co.begin(), co.end());
co.resize(unique(co.begin(), co.end()) - co.begin());
}
bool dd[N];
int special;
bool dfs1(int u, int pre, int cw) {
if (u == special) return 1;
bool ret = 0;
for (auto duck : ad[u]) {
int v, w; tie(v, w) = duck;
if (v == pre || w > cw) continue;
if (!dd[v]) {
dd[v] = 1;
ret |= dfs1(v, u, cw);
}
}
return ret;
}
bool dfs2(int u, int pre, int cw) {
int cnt = pre != -1;
bool ret = 0;
map<int, int> d;
for (auto duck : ad[u]) {
int v, w; tie(v, w) = duck;
if (v == pre || w > cw) continue;
if (dd[v] && !d[v]) return 1;
if (!dd[v]) {
dd[v] = d[v] = 1;
cnt += 1;
ret |= dfs2(v, u, cw);
}
}
return (cnt > 2 || ret);
}
int getMinimumFuelCapacity(int X, int Y) {
if (m == n - 1) {
if (sub1) return -1;
int answer = 1e9 + 1;
int l = lca(X, Y);
if (anc(Y, X)) swap(X, Y);
if (!anc(X, Y)) answer = min(answer, dpin[X]);
answer = min({answer, dpin[Y], binary_jump(X, Y)});
int maxw = wmax(X, Y);
if (X != l && Y != l) {
if (ad[l].size() >= 3) {
for (int i = 16; i >= 0; --i) if (!anc(f[X][i], Y)) X = f[X][i];
for (int i = 16; i >= 0; --i) if (!anc(f[Y][i], X)) Y = f[Y][i];
int it = 0;
while (ad[l][it].first == X || ad[l][it].first == Y) it += 1;
answer = min(answer, ad[l][it].second);
}
} else {
answer = min({answer, dpout[Y]});
}
answer = max(answer, maxw);
return answer;
}
int l = 0, r = co.size() - 1;
int answer = -1;
special = Y;
while (l <= r) {
int mid = l + r >> 1;
bool ret = 1;
memset(dd, 0, sizeof dd); ret &= dfs1(X, -1, co[mid]);
memset(dd, 0, sizeof dd); ret &= dfs2(X, -1, co[mid]);
if (ret) r = mid - 1, answer = co[mid];
else l = mid + 1;
}
return answer;
}
#ifdef LOCAL
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
if (fopen("duck.inp", "r")) {
freopen("duck.inp", "r", stdin);
freopen("duck.out", "w", stdout);
}
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;
for (int i = 1; i <= q; ++i) {
int X, Y; cin >> X >> Y;
cout << getMinimumFuelCapacity(X, Y) << '\n';
}
}
#endif // LOCAL
Compilation message
swap.cpp: In function 'bool dfs2(int, int, int)':
swap.cpp:188:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
188 | dd[v] = d[v] = 1;
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:234:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
234 | int mid = l + r >> 1;
| ~~^~~
swap.cpp: In function 'int32_t main()':
swap.cpp:252:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
252 | freopen("duck.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
swap.cpp:253:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
253 | freopen("duck.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc62C3ag.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccvh1enf.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
