#include "swap.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int inf = 2e9; int par[MAXN], comp_size[MAXN], merged[MAXN], time_valid[MAXN], deg[MAXN]; int find(int a) { while (par[a] != a) a = par[a]; return a; } void join(int u, int v, int time) { deg[u]++; deg[v]++; int a = find(u); int b = find(v); // A component is swappable if an internal node has degree >= 3 or it has a cycle bool swappable_now = (deg[u] >= 3 || deg[v] >= 3 || a == b); // [cite: 124, 125, 136] if (a == b) { time_valid[a] = min(time_valid[a], time); return; } if (comp_size[a] < comp_size[b]) swap(a, b); // Inheritance: If either child was already swappable, // the new component is swappable at the time they merge. if (time_valid[a] < inf || time_valid[b] < inf || swappable_now) { time_valid[a] = min({time_valid[a], time_valid[b], time}); // } par[b] = a; comp_size[a] += comp_size[b]; merged[b] = time; // Time when b was merged into a parent } void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) { for (int i = 0; i < n; i++) { comp_size[i] = 1; par[i] = i; time_valid[i] = inf; merged[i] = -1; // Use -1 to distinguish from a 0-weight edge deg[i] = 0; } vector<int> edges(m); iota(edges.begin(), edges.end(), 0); sort(edges.begin(), edges.end(), [&](int a, int b) { return W[a] < W[b]; }); for (int i : edges) { join(U[i], V[i], W[i]); } } int getMinimumFuelCapacity(int X, int Y) { int merge_time = 0; int x = X, y = Y; // 1. Find the LCA and the time X and Y first connected while (x != y) { if (comp_size[x] > comp_size[y]) swap(x, y); if (par[x] == x) break; // Reached root merge_time = max(merge_time, merged[x]); x = par[x]; } if (x != y) return -1; // Not in same component [cite: 131] // 2. Climb to the root to find the earliest swappable ancestor // The answer is the weight of the node where the component first became swappable int x_swappable = x; int best_valid = inf; // Walk up from the meeting point to find the lowest ancestor that is swappable int curr = x; while (true) { if (time_valid[curr] < inf) { best_valid = max(merge_time, time_valid[curr]); break; } if (par[curr] == curr) break; merge_time = max(merge_time, merged[curr]); curr = par[curr]; } if (best_valid == inf) return -1; return best_valid; }