#include "swap.h"
#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 2e5 + 7;
const int Mod = 998244353;
const int szBL = 916;
const int INF = 1e9;
const int BASE = 137;
struct Edge {
int u, v, w;
};
vector<int> weights;
struct Query {
int X, Y;
int id;
int lf, rt, ok;
int getMid() { return lf + rt >> 1; }
};
struct Disjoin_set {
int lab[N], sz[N];
bool isline[N];
pair<int,int> ln[N];
void init (int n) {
rep (i, 1, n) {
lab[i] = i;
sz[i] = 1;
isline[i] = 1;
ln[i] = {i, i};
}
}
int Find (int u) {
return u == lab[u] ? u : lab[u] = Find(lab[u]);
}
void Join (int u, int v){
int uu = u, vv = v;
u = Find(u);
v = Find(v);
if (u == v) {
isline[u] = 0;
return;
}
if (sz[u] < sz[v]) swap (u, v), swap (uu, vv);
if (min(isline[v], isline[u]) == 0) {
isline[u] = isline[v] = 0;
}
else {
if ((uu != ln[u].fs && uu != ln[u].se) || (vv != ln[v].fs && vv != ln[v].se)) {
isline[u] = isline[v] = 0;
}
else {
static vector<int> vec;
if (ln[u].fs == ln[u].se) {
if (ln[v].fs != vv) ln[u].se = ln[v].fs;
else ln[u].se = ln[v].se;
}
else if (ln[v].fs == ln[v].se) {
if (ln[u].fs != uu) ln[u].se = ln[v].fs;
else ln[u].fs = ln[v].fs;
}
else {
vec = {ln[u].fs, ln[u].se, ln[v].fs, ln[v].se};
ln[u] = {-1, -1};
iter (&id, vec) {
if (id != uu && id != vv) {
if (ln[u].fs == -1) ln[u].fs = id;
else ln[u].se = id;
}
}
}
}
}
lab[v] = u;
sz[u] += sz[v];
}
bool check (int u, int v) {
u = Find(u);
v = Find(v);
if (u != v) return 0;
return isline[u] == 0;
}
}DSU;
int n, m, Q;
vector<Edge> edges;
Query qr[N];
map<pair<int,int>, int> Ans;
void algo() {
sort (ALL(edges), [] (Edge A, Edge B) { return A.w < B.w; });
iter (&E, edges) weights.push_back(E.w);
sort (ALL(weights));
weights.resize (unique(ALL(weights)) - weights.begin());
rep (i, 1, Q) {
qr[i].lf = 0;
qr[i].rt = SZ(weights) - 1;
qr[i].ok = 0;
}
rep (step, 0, 25) {
DSU.init(n);
sort (qr + 1, qr + 1 + Q, [] (Query A, Query B) { return A.getMid() < B.getMid(); });
int ptrQ = 1, ptrE = 0;
iter (&W, weights) {
while (ptrE < SZ(edges) && edges[ptrE].w < W) ++ptrE;
while (ptrQ <= Q && weights[qr[ptrQ].getMid()] < W) ++ptrQ;
while (ptrE < SZ(edges) && edges[ptrE].w == W) {
Edge &cur = edges[ptrE];
DSU.Join(cur.u, cur.v);
++ptrE;
}
while (ptrQ <= Q && weights[qr[ptrQ].getMid()] == W) {
Query &cur = qr[ptrQ];
if (DSU.check(cur.X, cur.Y)) {
qr[ptrQ].rt = qr[ptrQ].getMid();
qr[ptrQ].ok = 1;
}
else qr[ptrQ].lf = qr[ptrQ].getMid() + 1;
++ptrQ;
}
}
}
sort (qr + 1, qr + 1 + Q, [] (Query A, Query B) { return A.id < B.id; });
// rep (i, 1, Q) {
// if (qr[i].ok == 1) {
//// cout << weights[qr[i].getMid()] <<"\n";
// Ans[mp(qr[i].X, qr[i].Y)] = weights[qr[i].getMid()];
// }
// else {
// Ans[mp(qr[i].X, qr[i].Y)] = -1;
//// cout << -1 <<"\n";
// }
// }
}
void init (int _n, int _m, vector<int> _U, vector<int> _V, vector<int> _W) {
//void solution() {
n = _n;
m = _m;
Q = _Q;
rep (i, 0, m - 1) {
int u = _U[i], v = _V[i], w = _W[i];
++u, ++v;
edges.push_back({u, v, w});
}
rep (i, 0, Q - 1) {
qr[i + 1].X = _X[i] + 1, qr[i + 1].Y = _Y[i] + 1;
}
// cin >> n >> m;
// rep (i, 1, m) {
// int u, v, w;
// cin >> u >> v >> w;
// ++u,++v;
// edges.push_back({u, v, w});
// }
// cin >> Q;
// rep (i, 1, Q ) {
// cin >> qr[i].X >> qr[i].Y;
// ++qr[i].X, ++qr[i].Y;
// qr[i].id = i;
// }
// algo();
}
int getMinimumFuelCapacity (int X, int Y) {
Q = 1;
qr[1].X = ++X, qr[1].Y = ++Y;
algo();
if (qr[i].ok == 1) {
//// cout << weights[qr[i].getMid()] <<"\n";
return weights[qr[i].getMid()];
else return -1;
// Ans[mp(qr[i].X, qr[i].Y)] = weights[qr[i].getMid()];
// }
// else {
// Ans[mp(qr[i].X, qr[i].Y)] = -1;
//// cout << -1 <<"\n";
// }
}
//#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
//int main () {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//// file ("c");
// int num_Test = 1;
//// cin >> num_Test;
// while (num_Test--)
// solution();
//}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
3 2
0 1 5
0 2 5
1
1 2
*/
Compilation message
swap.cpp: In member function 'int Query::getMid()':
swap.cpp:39:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int getMid() { return lf + rt >> 1; }
| ~~~^~~~
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:165:9: error: '_Q' was not declared in this scope; did you mean '_n'?
165 | Q = _Q;
| ^~
| _n
swap.cpp:172:23: error: '_X' was not declared in this scope; did you mean '_n'?
172 | qr[i + 1].X = _X[i] + 1, qr[i + 1].Y = _Y[i] + 1;
| ^~
| _n
swap.cpp:172:48: error: '_Y' was not declared in this scope; did you mean '_n'?
172 | qr[i + 1].X = _X[i] + 1, qr[i + 1].Y = _Y[i] + 1;
| ^~
| _n
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:194:12: error: 'i' was not declared in this scope
194 | if (qr[i].ok == 1) {
| ^
swap.cpp:197:5: error: expected '}' before 'else'
197 | else return -1;
| ^~~~
swap.cpp:194:24: note: to match this '{'
194 | if (qr[i].ok == 1) {
| ^
