제출 #965941

#제출 시각아이디문제언어결과실행 시간메모리
965941Pring자매 도시 (APIO20_swap)C++17
0 / 100
190 ms27752 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]; 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); }

컴파일 시 표준 에러 (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: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 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...