Submission #965886

#TimeUsernameProblemLanguageResultExecution timeMemory
965886PringSwapping Cities (APIO20_swap)C++17
0 / 100
214 ms29640 KiB
#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] + a[2]; if (a[1] == x) return a[0] + a[2]; return a[0] + a[1]; } }; 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], C; int ep[MXN], ed[MXN]; 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++; 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); } 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], vs[x].CMP2(ep[x])); while (top[x] != top[rt]) { ans = min(ans, smg.query(dfn[top[x]], dfn[x] + 1)); ww = ep[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, ed[rt]); } } 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, epp] = TREE::CHAIN(y, x); // return min(ans, vs[y].CMP(epp)); return min(ans, vs[y].CMP2(epp)); } auto [ansl, eppl] = TREE::CHAIN(lca, x); auto [ansr, eppr] = TREE::CHAIN(lca, y); return min(min(ansl, ansr), vs[lca].CMP(eppl, eppr)); } } 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 (stderr)

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:203:9: note: in expansion of macro 'debug'
  203 |         debug(x, y, lca);
      |         ^~~~~
swap.cpp: In function 'pii {anonymous}::TREE::CHAIN(int, int)':
swap.cpp:157:28: warning: 'ww' may be used uninitialized in this function [-Wmaybe-uninitialized]
  157 |             int ans = INF, ww;
      |                            ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...