結果
問題 | No.1326 ふたりのDominator |
ユーザー |
![]() |
提出日時 | 2020-12-23 02:32:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 143 ms / 2,000 ms |
コード長 | 12,058 bytes |
コンパイル時間 | 3,135 ms |
コンパイル使用メモリ | 227,860 KB |
最終ジャッジ日時 | 2025-01-17 06:21:39 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
#include<bits/stdc++.h>using namespace std;using int64 = long long;//const int mod = 1e9 + 7;const int mod = 998244353;const int64 infll = (1LL << 62) - 1;const int inf = (1 << 30) - 1;struct IoSetup {IoSetup() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(10);cerr << fixed << setprecision(10);}} iosetup;template< typename T1, typename T2 >ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {os << p.first << " " << p.second;return os;}template< typename T1, typename T2 >istream &operator>>(istream &is, pair< T1, T2 > &p) {is >> p.first >> p.second;return is;}template< typename T >ostream &operator<<(ostream &os, const vector< T > &v) {for(int i = 0; i < (int) v.size(); i++) {os << v[i] << (i + 1 != v.size() ? " " : "");}return os;}template< typename T >istream &operator>>(istream &is, vector< T > &v) {for(T &in : v) is >> in;return is;}template< typename T1, typename T2 >inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }template< typename T1, typename T2 >inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }template< typename T = int64 >vector< T > make_v(size_t a) {return vector< T >(a);}template< typename T, typename... Ts >auto make_v(size_t a, Ts... ts) {return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));}template< typename T, typename V >typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {t = v;}template< typename T, typename V >typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {for(auto &e : t) fill_v(e, v);}template< typename F >struct FixPoint : F {FixPoint(F &&f) : F(forward< F >(f)) {}template< typename... Args >decltype(auto) operator()(Args &&... args) const {return F::operator()(*this, forward< Args >(args)...);}};template< typename F >inline decltype(auto) MFP(F &&f) {return FixPoint< F >{forward< F >(f)};}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 > >;/*** @brief Low-Link(橋/関節点)* @see http://kagamiz.hatenablog.com/entry/2013/10/05/005213* @docs docs/low-link.md*/template< typename T = int >struct LowLink : Graph< T > {public:using Graph< T >::Graph;vector< int > ord, low, articulation;vector< Edge< T > > bridge;using Graph< T >::g;virtual void build() {used.assign(g.size(), 0);ord.assign(g.size(), 0);low.assign(g.size(), 0);int k = 0;for(int i = 0; i < (int) g.size(); i++) {if(!used[i]) k = dfs(i, k, -1);}}explicit LowLink(const Graph< T > &g) : Graph< T >(g) {}private:vector< int > used;int dfs(int idx, int k, int par) {used[idx] = true;ord[idx] = k++;low[idx] = ord[idx];bool is_articulation = false, beet = false;int cnt = 0;for(auto &to : g[idx]) {if(to == par && !exchange(beet, true)) {continue;}if(!used[to]) {++cnt;k = dfs(to, k, idx);low[idx] = min(low[idx], low[to]);is_articulation |= par >= 0 && low[to] >= ord[idx];if(ord[idx] < low[to]) bridge.emplace_back(to);} else {low[idx] = min(low[idx], ord[to]);}}is_articulation |= par == -1 && cnt > 1;if(is_articulation) articulation.push_back(idx);return k;}};/*** @brief Bi-Connected-Components(二重頂点連結成分分解)* @docs docs/bi-connected-components.md*/template< typename T = int >struct BiConnectedComponents : LowLink< T > {public:using LowLink< T >::LowLink;using LowLink< T >::g;using LowLink< T >::ord;using LowLink< T >::low;vector< vector< Edge< T > > > bc;void build() override {LowLink< T >::build();used.assign(g.size(), 0);for(int i = 0; i < used.size(); i++) {if(!used[i]) dfs(i, -1);}}explicit BiConnectedComponents(const Graph< T > &g) : Graph< T >(g) {}private:vector< int > used;vector< Edge< T > > tmp;void dfs(int idx, int par) {used[idx] = true;bool beet = false;for(auto &to : g[idx]) {if(to == par && !exchange(beet, true)) continue;if(!used[to] || ord[to] < ord[idx]) {tmp.emplace_back(to);}if(!used[to]) {dfs(to, idx);if(low[to] >= ord[idx]) {bc.emplace_back();for(;;) {auto e = tmp.back();bc.back().emplace_back(e);tmp.pop_back();if(e.idx == to.idx) break;}}}}}};/*** @brief Block-Cut-Tree* @see https://ei1333.hateblo.jp/entry/2020/03/25/010057*/template< typename T = int >struct BlockCutTree : BiConnectedComponents< T > {public:using BiConnectedComponents< T >::BiConnectedComponents;using BiConnectedComponents< T >::g;using BiConnectedComponents< T >::articulation;using BiConnectedComponents< T >::bc;vector< int > rev;vector< vector< int > > group;Graph< T > tree;explicit BlockCutTree(const Graph< T > &g) : Graph< T >(g) {}int operator[](const int &k) const {return rev[k];}void build() override {BiConnectedComponents< T >::build();rev.assign(g.size(), -1);int ptr = (int) bc.size();for(auto &idx : articulation) {rev[idx] = ptr++;}vector< int > last(ptr, -1);tree = Graph< T >(ptr);for(int i = 0; i < (int) bc.size(); i++) {for(auto &e : bc[i]) {for(auto &ver : {e.from, e.to}) {if(rev[ver] >= (int) bc.size()) {if(exchange(last[rev[ver]], i) != i) {tree.add_edge(rev[ver], i, e.cost);}} else {rev[ver] = i;}}}}group.resize(ptr);for(int i = 0; i < (int) g.size(); i++) {group[rev[i]].emplace_back(i);}}};/*** @brief Sparse-Table(スパーステーブル)* @docs docs/sparse-table.md*/template< typename T, typename F >struct SparseTable {F f;vector< vector< T > > st;vector< int > lookup;SparseTable() = default;explicit SparseTable(const vector< T > &v, const F &f) : f(f) {const int n = (int) v.size();const int b = 32 - __builtin_clz(n);st.assign(b, vector< T >(n));for(int i = 0; i < v.size(); i++) {st[0][i] = v[i];}for(int i = 1; i < b; i++) {for(int j = 0; j + (1 << i) <= n; j++) {st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);}}lookup.resize(v.size() + 1);for(int i = 2; i < lookup.size(); i++) {lookup[i] = lookup[i >> 1] + 1;}}inline T fold(int l, int r) const {int b = lookup[r - l];return f(st[b][l], st[b][r - (1 << b)]);}};template< typename T, typename F >SparseTable< T, F > get_sparse_table(const vector< T > &v, const F &f) {return SparseTable< T, F >(v, f);}/*** @brief Plus-Minus-One-RMQ**/template< typename T >struct PlusMinusOneRMQ {using F = function< int(int, int) >;int backet;vector< T > vs;vector< int > bidx, bbit;SparseTable< int, F > st;vector< vector< vector< int > > > lookup;explicit PlusMinusOneRMQ() = default;explicit PlusMinusOneRMQ(const vector< T > &vs) : vs(vs) {int n = (int) vs.size();backet = max(1, (31 - __builtin_clz(n)) / 2);int sz = (n + backet - 1) / backet;bidx.assign(sz, -1);bbit.assign(sz, 0);for(int i = 0; i < sz; i++) {int l = i * backet;int r = min(l + backet, n);bidx[i] = l;for(int j = l + 1; j < r; j++) {if(vs[j] < vs[bidx[i]]) bidx[i] = j;if(vs[j - 1] < vs[j]) bbit[i] |= 1 << (j - l - 1);}}F f = [&](int a, int b) { return vs[a] < vs[b] ? a : b; };st = get_sparse_table(bidx, f);lookup.assign(1 << (backet - 1), vector< vector< int > >(backet, vector< int >(backet + 1)));for(int i = 0; i < (1 << (backet - 1)); i++) {for(int j = 0; j < backet; j++) {int sum = 0, ret = 0, pos = j;for(int k = j + 1; k <= backet; k++) {lookup[i][j][k] = pos;if(i & (1 << (k - 1))) ++sum;else --sum;if(sum < ret) {pos = k;ret = sum;}}}}}pair< T, int > fold(int l, int r) const {int lb = l / backet;int rb = r / backet;if(lb == rb) {int pos = lb * backet + lookup[bbit[lb]][l % backet][r % backet];return {vs[pos], pos};}int pos = lb * backet + lookup[bbit[lb]][l % backet][backet];if(r % backet > 0) {int sub = rb * backet + lookup[bbit[rb]][0][r % backet];if(vs[sub] < vs[pos]) pos = sub;}if(lb + 1 == rb) {return {vs[pos], pos};} else {int sub = st.fold(lb + 1, rb);if(vs[sub] < vs[pos]) pos = sub;return {vs[pos], pos};}}};/*** @brief PMORMQ-Lowest-Common-Ancestor(最小共通祖先)* @docs docs/pmormq-lowest-common-ancestor.md**/template< typename T = int >struct PMORMQLowestCommonAncestor : Graph< T > {public:using Graph< T >::Graph;using Graph< T >::g;using F = function< int(int, int) >;void build(int root = 0) {ord.reserve(g.size() * 2 - 1);dep.reserve(g.size() * 2 - 1);in.resize(g.size());dfs(root, -1, 0);vector< int > vs(g.size() * 2 - 1);iota(begin(vs), end(vs), 0);st = PlusMinusOneRMQ< int >(dep);}int lca(int x, int y) const {if(in[x] > in[y]) swap(x, y);return ord[st.fold(in[x], in[y] + 1).second];}explicit PMORMQLowestCommonAncestor(const Graph< T > &g) : Graph< T >(g) {}private:vector< int > ord, dep, in;PlusMinusOneRMQ< int > st;void dfs(int idx, int par, int d) {in[idx] = (int) ord.size();ord.emplace_back(idx);dep.emplace_back(d);for(auto &to : g[idx]) {if(to != par) {dfs(to, idx, d + 1);ord.emplace_back(idx);dep.emplace_back(d);}}}};int main() {int N, M;cin >> N >> M;BlockCutTree<> g(N);g.read(M);g.build();PMORMQLowestCommonAncestor<> bct(g.tree);bct.build();vector< int > sum(g.tree.size());MFP([&](auto rec, int idx, int par) -> void {if(idx >= g.bc.size()) {sum[idx]++;}for(auto &to : g.tree.g[idx]) {if(to != par) {sum[to] += sum[idx];rec(to, idx);}}})(0, -1);int Q;cin >> Q;while(Q--) {int X, Y;cin >> X >> Y;--X, --Y;X = g[X];Y = g[Y];if(X == Y) {cout << 0 << "\n";continue;}int lca = bct.lca(X, Y);if(X == lca) {swap(X, Y);}if(Y == lca) {int ans = sum[X] - sum[Y];ans -= X >= g.bc.size();cout << ans << "\n";continue;}int ans = sum[X] + sum[Y] - 2 * sum[lca];ans -= X >= g.bc.size();ans -= Y >= g.bc.size();ans += lca >= g.bc.size();cout << ans << "\n";}}