#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef array<int, 3> p3i;
namespace {
const int MXN = 100005, INF = 1e9;
int n, m;
vector<int> eu, ev, ew;
vector<pii> edge[MXN];
struct P {
int a[3];
P() {
fill(a, a + 3, INF);
}
void ADD(int x) {
if (x < a[0]) {
a[2] = a[1];
a[1] = a[0];
a[0] = x;
} else if (x < a[1]) {
a[2] = a[1];
a[1] = x;
} else a[2] = min(a[2], x);
}
int CMP(int x, int y = INF) {
if (x > y) swap(x, y);
if (a[0] != x) return a[0];
return (a[1] == y ? a[2] : a[1]);
}
int CMP2(int x) {
if (a[0] == x) return a[1];
return a[0];
}
};
vector<P> vs;
int ori[MXN];
struct DSU {
int p[MXN];
void init(int n) {
fill(p + 1, p + n + 1, -1);
}
int find(int x) {
return (p[x] < 0 ? x : p[x] = find(p[x]));
}
bool onion(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (p[x] > p[y]) swap(x, y);
p[x] += p[y];
p[y] = x;
return true;
}
} dsu;
struct SMG {
int n, val[MXN * 2];
void init(int _n, int *a) {
n = _n;
copy(a, a + n, val + n);
for (int i = n - 1; i; i--) {
val[i] = min(val[i << 1], val[i << 1 | 1]);
}
}
void modify(int p, int v) {
val[p + n] = v;
for (int x = (p + n) >> 1; x; x >>= 1) val[x] = min(val[x << 1], val[x << 1 | 1]);
}
int query(int l, int r) {
int ans = INF;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans = min(ans, val[l++]);
if (r & 1) ans = min(ans, val[--r]);
}
return ans;
}
} smg;
namespace TREE {
vector<pii> edge[MXN];
int p[MXN], d[MXN], sz[MXN], son[MXN], top[MXN], dfn[MXN], idfn[MXN], C;
int ep[MXN], ed[MXN];
namespace DP {
pair<pii, pii> down[MXN];
void PUSH(int id, pii p) {
if (p > down[id].fs) {
down[id].sc = down[id].fs;
down[id].fs = p;
} else down[id].sc = min(down[id].sc, p);
}
int DFS1(int id, int par) {
int ans = vs[id].CMP2(ep[par]);
down[id].fs = mp(INF, -1);
down[id].sc = mp(INF, -1);
for (auto &[w, i] : edge[id]) {
if (i == par) continue;
int val = DFS1(i, id);
PUSH(id, mp(max(w, val), id));
ans = min(ans, val);
}
return ans;
}
int QUERY(int id, int x) {
int ans = vs[id].CMP2((d[id] > d[x] ? ep[id] : ep[x]));
if (x == down[id].fs.sc) ans = min(ans, down[id].sc.fs);
else ans = min(ans, down[id].fs.fs);
return ans;
}
void DFS2(int id, int par) {
if (par) {
PUSH(id, mp(max(ep[id], QUERY(par, id)), par));
}
for (auto &[_, i] : edge[id]) {
if (i == par) continue;
DFS2(i, id);
}
}
}
void ADD_EDGE(int x, int y, int w) {
edge[x].push_back(mp(w, y));
edge[y].push_back(mp(w, x));
}
void DFS(int id, int par, int dep) {
p[id] = par;
d[id] = dep;
sz[id] = 1;
for (auto &[w, i] : edge[id]) {
if (i == par) continue;
DFS(i, id, dep + 1);
sz[id] += sz[i];
if (!son[id]) son[id] = i;
else if (sz[son[id]] < sz[i]) son[id] = i;
}
}
void HLD(int id, int par, int _t) {
top[id] = _t;
dfn[id] = C++;
idfn[dfn[id]] = id;
ep[id] = INF;
ed[id] = INF;
if (son[id]) HLD(son[id], id, _t);
for (auto &[w, i] : edge[id]) {
if (i == par) {
ep[id] = w;
} else if (i == son[id]) {
ed[id] = w;
} else {
HLD(i, id, i);
}
}
}
void BUILD() {
DFS(1, 0, 0);
HLD(1, 0, 1);
FOR(i, 1, n + 1) ori[dfn[i]] = vs[i].CMP(ep[i], ed[i]);
smg.init(n, ori);
DP::DFS1(1, 0);
DP::DFS2(1, 0);
}
int LCA(int x, int y) {
while (top[x] != top[y]) {
if (d[top[x]] < d[top[y]]) swap(x, y);
x = p[top[x]];
}
return (d[x] > d[y] ? y : x);
}
pii CHAIN(int rt, int x) {
int ans = INF, ww;
vector<int> st;
st.push_back(x);
smg.modify(dfn[x], INF);
while (top[x] != top[rt]) {
ans = min(ans, smg.query(dfn[top[x]], dfn[x] + 1));
ww = top[x];
x = p[top[x]];
st.push_back(x);
smg.modify(dfn[x], vs[x].CMP(ep[x], ww));
}
if (x == rt) {
for (auto &i : st) {
smg.modify(dfn[i], ori[i]);
}
return mp(ans, ww);
}
ans = min(ans, smg.query(dfn[rt] + 1, dfn[x] + 1));
for (auto &i : st) {
smg.modify(dfn[i], ori[i]);
}
return mp(ans, idfn[dfn[rt] + 1]);
}
}
void BUILD() {
// vector<p3i> v;
// FOR(i, 0, m) v.push_back({ew[i], eu[i], ev[i]});
// sort(v.begin(), v.end());
// FOR(i, 0, m) {
// eu[i] = v[i][1];
// ev[i] = v[i][2];
// ew[i] = v[i][0];
// }
vs = vector<P>(n + 1, P());
dsu.init(n);
FOR(i, 0, m) {
vs[eu[i]].ADD(ew[i]);
vs[ev[i]].ADD(ew[i]);
if (dsu.onion(eu[i], ev[i])) TREE::ADD_EDGE(eu[i], ev[i], ew[i]);
}
TREE::BUILD();
}
int QUERY(int x, int y) {
if (TREE::d[x] < TREE::d[y]) swap(x, y);
int lca = TREE::LCA(x, y);
debug(x, y, lca);
if (lca == y) {
auto [ans, lst] = TREE::CHAIN(y, x);
return min(ans, min(TREE::DP::QUERY(x, TREE::p[x]), TREE::DP::QUERY(y, lst)));
}
auto [ansl, _1] = TREE::CHAIN(lca, x);
auto [ansr, _2] = TREE::CHAIN(lca, y);
return min(min(min(ansl, ansr), min(TREE::DP::QUERY(x, TREE::p[x]), TREE::DP::QUERY(y, TREE::p[y]))), vs[lca].CMP(TREE::ep[_1], TREE::ep[_2]));
}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
::n = N;
::m = M;
assert(m == n - 1);
FOR(i, 0, m) {
edge[++U[i]].push_back(mp(W[i], ++V[i]));
edge[V[i]].push_back(mp(W[i], U[i]));
}
::eu = U;
::ev = V;
::ew = W;
BUILD();
}
int getMinimumFuelCapacity(int X, int Y) {
int x = QUERY(++X, ++Y);
return (x == ::INF ? -1 : x);
}
Compilation message
swap.cpp: In function 'int {anonymous}::QUERY(int, int)':
swap.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 39
| ^~
swap.cpp:248:9: note: in expansion of macro 'debug'
248 | debug(x, y, lca);
| ^~~~~
swap.cpp: In function 'pii {anonymous}::TREE::CHAIN(int, int)':
swap.cpp:202:28: warning: 'ww' may be used uninitialized in this function [-Wmaybe-uninitialized]
202 | int ans = INF, ww;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 2 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
11612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 2 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 3 |
Incorrect |
190 ms |
27752 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 2 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
11612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 2 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
11612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 2 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
11612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 2 |
Correct |
2 ms |
11612 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
11612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
