結果
問題 | No.1326 ふたりのDominator |
ユーザー | りあん |
提出日時 | 2020-12-23 01:13:02 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 367 ms / 2,000 ms |
コード長 | 6,878 bytes |
コンパイル時間 | 2,788 ms |
コンパイル使用メモリ | 225,752 KB |
実行使用メモリ | 23,848 KB |
最終ジャッジ日時 | 2023-10-24 10:34:00 |
合計ジャッジ時間 | 8,198 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 3 ms
4,348 KB |
testcase_03 | AC | 3 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 5 ms
4,348 KB |
testcase_08 | AC | 5 ms
4,348 KB |
testcase_09 | AC | 5 ms
4,348 KB |
testcase_10 | AC | 5 ms
4,348 KB |
testcase_11 | AC | 5 ms
4,348 KB |
testcase_12 | AC | 294 ms
17,132 KB |
testcase_13 | AC | 290 ms
17,132 KB |
testcase_14 | AC | 293 ms
17,136 KB |
testcase_15 | AC | 295 ms
17,428 KB |
testcase_16 | AC | 297 ms
17,580 KB |
testcase_17 | AC | 301 ms
18,624 KB |
testcase_18 | AC | 360 ms
22,680 KB |
testcase_19 | AC | 291 ms
17,920 KB |
testcase_20 | AC | 314 ms
17,828 KB |
testcase_21 | AC | 333 ms
18,104 KB |
testcase_22 | AC | 367 ms
23,848 KB |
testcase_23 | AC | 259 ms
15,984 KB |
testcase_24 | AC | 298 ms
17,132 KB |
ソースコード
// from: https://judge.yosupo.jp/submission/6489 #include <bits/stdc++.h> using namespace std; using int64 = long long; template< typename T = int > struct Edge { int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} operator int() const { return to; } }; template< typename T = int > struct Graph { vector< vector< Edge< T > > > g; int es; Graph() = default; explicit Graph(int n) : g(n), es(0) {} size_t size() const { return g.size(); } void add_directed_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es++); } void add_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es); g[to].emplace_back(to, from, cost, es++); } void read(int M, int padding = -1, bool weighted = false, bool directed = false) { for(int i = 0; i < M; i++) { int a, b; cin >> a >> b; a += padding; b += padding; T c = T(1); if(weighted) cin >> c; if(directed) add_directed_edge(a, b, c); else add_edge(a, b, c); } } }; template< typename T = int > using Edges = vector< Edge< T > >; template< typename T = int > struct DominatorTree : Graph< T > { public: using Graph< T >::Graph; using Graph< T >::g; void build(int root) { rg = Graph< T >(g.size()); par.assign(g.size(), 0); idom.assign(g.size(), -1); semi.assign(g.size(), -1); ord.reserve(g.size()); UnionFind uf(semi); const int N = (int) g.size(); dfs(root); for(int i = 0; i < N; i++) { for(auto &to : g[i]) { if(~semi[i]) rg.add_directed_edge(to, i); } } vector< vector< int > > bucket(N); vector< int > U(N); for(int i = (int) ord.size() - 1; i >= 0; i--) { int x = ord[i]; for(int v : rg.g[x]) { v = uf.eval(v); if(semi[x] > semi[v]) semi[x] = semi[v]; } bucket[ord[semi[x]]].emplace_back(x); for(int v : bucket[par[x]]) U[v] = uf.eval(v); bucket[par[x]].clear(); uf.link(par[x], x); } for(int i = 1; i < ord.size(); i++) { int x = ord[i], u = U[x]; idom[x] = semi[x] == semi[u] ? semi[x] : idom[u]; } for(int i = 1; i < ord.size(); i++) { int x = ord[i]; idom[x] = ord[idom[x]]; } idom[root] = root; } int operator[](const int &k) const { return idom[k]; } private: Graph< T > rg; struct UnionFind { const vector< int > ; vector< int > par, m; explicit UnionFind(const vector< int > &semi) : semi(semi), par(semi.size()), m(semi.size()) { iota(begin(par), end(par), 0); iota(begin(m), end(m), 0); } int find(int v) { if(par[v] == v) return v; int r = find(par[v]); if(semi[m[v]] > semi[m[par[v]]]) m[v] = m[par[v]]; return par[v] = r; } int eval(int v) { find(v); return m[v]; } void link(int p, int c) { par[c] = p; } }; vector< int > ord, par; vector< int > idom, semi; void dfs(int idx) { semi[idx] = (int) ord.size(); ord.emplace_back(idx); for(auto &to : g[idx]) { if(~semi[to]) continue; dfs(to); par[to] = idx; } } }; struct dsu { public: dsu() : _n(0) {} dsu(int n) : _n(n), parent_or_size(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } std::vector<std::vector<int>> groups() { std::vector<int> leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector<std::vector<int>> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }), result.end()); return result; } private: int _n; // root node: -1 * component size // otherwise: parent std::vector<int> parent_or_size; }; int dfs(int p, const DominatorTree<>& g, vector<int>& dep, int root) { if (dep[p] != -1) return dep[p]; if (p == root) return dep[p] = 0; return dep[p] = dfs(g[p], g, dep, root) + 1; } void climb(int& p, const vector<vector<int>>& par, int k) { for (int i = 19; i >= 0; --i) { if ((k >> i) & 1) { p = par[i][p]; } } } int lca(int& p, int& q, const vector<vector<int>>& par) { // assert(p != q); int res = 0; for (int i = 19; i >= 0; --i) { if (par[i][p] != par[i][q]) { res += 1 << i; p = par[i][p]; q = par[i][q]; } } return res; } int main() { using P = pair<int, int>; int n, m; cin >> n >> m; vector<P> edge(m); DominatorTree<> g(n); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; --u; --v; g.add_edge(u, v); edge[i] = {u, v}; } int root = 0; g.build(root); dsu uf(n); for (auto& e : edge) { if (g[e.first] != e.second && g[e.second] != e.first) { uf.merge(e.first, e.second); } } vector<int> dep(n, -1); for (int i = 0; i < n; ++i) { if (dep[i] == -1) { dfs(i, g, dep, root); } } vector<vector<int>> par(20, vector<int>(n, -1)); for (int i = 0; i < n; ++i) { par[0][i] = g[i]; } for (int i = 0; i + 1 < 20; ++i) { for (int j = 0; j < n; ++j) { par[i + 1][j] = par[i][par[i][j]]; } } int q; cin >> q; for (int i = 0; i < q; ++i) { int x, y; cin >> x >> y; --x; --y; if (x == y) { cout << 0 << '\n'; continue; } int ans = 0; if (dep[x] > dep[y]) { ans += dep[x] - dep[y]; climb(x, par, dep[x] - dep[y]); } if (dep[x] < dep[y]) { ans += dep[y] - dep[x]; climb(y, par, dep[y] - dep[x]); } if (x == y) --ans; int k = lca(x, y, par); ans += k * 2; if (!uf.same(x, y)) { ++ans; } cout << ans << '\n'; } return 0; }