結果
問題 | No.1326 ふたりのDominator |
ユーザー | yuri3 |
提出日時 | 2023-06-27 05:34:52 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 169 ms / 2,000 ms |
コード長 | 6,419 bytes |
コンパイル時間 | 2,960 ms |
コンパイル使用メモリ | 225,752 KB |
実行使用メモリ | 42,200 KB |
最終ジャッジ日時 | 2024-07-03 23:57:17 |
合計ジャッジ時間 | 6,215 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 3 ms
6,940 KB |
testcase_08 | AC | 3 ms
6,940 KB |
testcase_09 | AC | 3 ms
6,944 KB |
testcase_10 | AC | 3 ms
6,940 KB |
testcase_11 | AC | 3 ms
6,940 KB |
testcase_12 | AC | 130 ms
26,720 KB |
testcase_13 | AC | 128 ms
26,460 KB |
testcase_14 | AC | 126 ms
26,488 KB |
testcase_15 | AC | 132 ms
26,324 KB |
testcase_16 | AC | 121 ms
25,416 KB |
testcase_17 | AC | 103 ms
21,188 KB |
testcase_18 | AC | 96 ms
17,368 KB |
testcase_19 | AC | 78 ms
20,736 KB |
testcase_20 | AC | 146 ms
38,404 KB |
testcase_21 | AC | 151 ms
38,344 KB |
testcase_22 | AC | 169 ms
42,200 KB |
testcase_23 | AC | 88 ms
22,692 KB |
testcase_24 | AC | 131 ms
26,592 KB |
ソースコード
#include <bits/stdc++.h> using i64 = std::int64_t; template <class G> struct BlockCutTree { G tree; std::vector<int> dfn, low; std::vector<int> ar; // cut vertex 1/0 std::vector<int> idar, idcc; std::vector<std::vector<int>> bcc; std::vector<std::vector<int>> aux; // block cut tree BlockCutTree(const G& tree) : tree(tree) { int sz = tree.size(); dfn.assign(sz, -1); low.assign(sz, -1); ar.assign(sz, 0); idar.assign(sz, -1); idcc.assign(sz, -1); build(); } void build() { int cnt = 0; std::stack<int> st; auto dfs = [&](auto&& self, int u, int fa) -> void { dfn[u] = low[u] = cnt++; int childCnt = 0; st.push(u); for (const auto& v : tree[u]) { if (v == fa) continue; if (dfn[v] == -1) { childCnt++; self(self, v, u); low[u] = std::min(low[u], low[v]); if (low[v] >= dfn[u]) { ar[u] = 1; std::vector<int> curBcc; while (true) { int cur = st.top(); curBcc.push_back(cur); st.pop(); if (cur == v) break; } curBcc.push_back(u); bcc.push_back(curBcc); } } else low[u] = std::min(low[u], dfn[v]); } if (fa < 0 && childCnt < 2) ar[u] = 0; }; for (int i = 0; i < (int)tree.size(); i++) { if (dfn[i] == -1) dfs(dfs, i, -1); } std::vector<int> arSet; for (int i = 0; i < (int)ar.size(); i++) if (ar[i]) arSet.push_back(i); for (int i = 0; i < (int)arSet.size(); i++) idar[arSet[i]] = i; aux.resize(arSet.size() + bcc.size()); std::vector<int> last(tree.size(), -1); for (int i = 0; i < (int)bcc.size(); i++) { auto add = [&](int i, int j) { if (i == -1 or j == -1) return; aux[i].push_back(j); aux[j].push_back(i); return; }; for (const auto& u : bcc[i]) { if (idar[u] == -1) idcc[u] = i + (int)arSet.size(); else if (last[u] != i) { add(i + (int)arSet.size(), idar[u]); last[u] = i; } } } } std::vector<int>& operator[](int i) { return aux[i]; } int size() const { return aux.size(); } int id(int i) { return idar[i] == -1 ? idcc[i] : idar[i]; } bool is_arti(int i) { return idar[i] != -1; } }; struct HLD { int n; int cnt; // dfs order [0,n) std::vector<std::vector<int>> adj; std::vector<int> par, dfn, hson, siz, top, dep; HLD() = delete; HLD(int _n) : n(_n), cnt(0), adj(_n), par(_n), dfn(_n), hson(_n), siz(_n), top(_n), dep(_n){}; HLD(std::vector<std::vector<int>> tr) { cnt = 0; n = tr.size(); adj = tr; par.resize(n), dfn.resize(n), hson.resize(n), siz.resize(n), top.resize(n), dep.resize(n); } void addEdge(int x, int y) { adj[x].push_back(y); adj[y].push_back(x); return; } void build(int root = 0) { auto dfs1 = [&](auto&& self, int u, int fa) -> void { par[u] = fa, siz[u] = 1, hson[u] = -1; for (const auto& v : adj[u]) { if (v == fa) continue; dep[v] = dep[u] + 1; self(self, v, u); siz[u] += siz[v]; if (hson[u] == -1) hson[u] = v; else if (siz[hson[u]] < siz[v]) hson[u] = v; } }; dfs1(dfs1, root, -1); auto dfs2 = [&](auto&& self, int u, int tp) -> void { dfn[u] = cnt++; top[u] = tp; if (hson[u] == -1) return; self(self, hson[u], tp); for (const auto& v : adj[u]) { if (v == par[u] || v == hson[u]) continue; self(self, v, v); } }; dfs2(dfs2, root, root); return; } int lca(int u, int v) const { while (top[u] != top[v]) { if (dep[top[u]] > dep[top[v]]) u = par[top[u]]; else v = par[top[v]]; } return ((dep[u] > dep[v]) ? v : u); } std::vector<std::pair<int, int>> pathP2P(int u, int v) const { // op length O(logn) std::vector<std::pair<int, int>> op; while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) std::swap(u, v); op.emplace_back(dfn[top[u]], dfn[u]); u = par[top[u]]; } if (dep[u] > dep[v]) std::swap(u, v); op.emplace_back(dfn[u], dfn[v]); return (op); } template <class F> void processP2P(int u, int v, F f) { // F: void(int L, int R) refers to the process of internal [L,R] while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) std::swap(u, v); f(dfn[top[u]], dfn[u]); u = par[top[u]]; } if (dep[u] > dep[v]) std::swap(u, v); f(dfn[u], dfn[v]); } }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<std::vector<int>> G(n); for (int i = 0; i < m; i++) { int x, y; std::cin >> x >> y; x--, y--; G[x].push_back(y); G[y].push_back(x); } BlockCutTree bct(G); HLD hld(bct.aux); hld.build(); int Q; std::cin >> Q; while (Q--) { int x, y; std::cin >> x >> y; x--, y--; if (x == y) { std::cout << 0 << '\n'; continue; } int ans = hld.dep[bct.id(x)]; ans += hld.dep[bct.id(y)]; ans -= hld.dep[hld.lca(bct.id(x), bct.id(y))] * 2; ans -= bct.ar[x]; ans -= bct.ar[y]; ans /= 2; std::cout << ans << '\n'; } return 0; }