#907401 (C++17) No.1326 ふたりのDominator

• 問題: No.1326 ふたりのDominator
• ユーザー: koba-e964
• 提出日時: 2023-08-25 12:11:45
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,800 ms / 2,000 ms
• コード長: 7,924 bytes
• コンパイル時間: 2,437 ms
• コンパイル使用メモリ: 163,348 KB
• 実行使用メモリ: 51,644 KB
• 最終ジャッジ日時: 2024-12-23 19:21:49
• 合計ジャッジ時間: 26,556 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	4 ms; 5,248 KB
testcase_03	AC	5 ms; 5,248 KB
testcase_04	AC	5 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	19 ms; 5,248 KB
testcase_08	AC	17 ms; 5,248 KB
testcase_09	AC	16 ms; 5,248 KB
testcase_10	AC	18 ms; 5,248 KB
testcase_11	AC	19 ms; 5,248 KB
testcase_12	AC	1,761 ms; 31,120 KB
testcase_13	AC	1,739 ms; 31,308 KB
testcase_14	AC	1,716 ms; 31,332 KB
testcase_15	AC	1,671 ms; 31,120 KB
testcase_16	AC	1,748 ms; 30,572 KB
testcase_17	AC	1,553 ms; 28,368 KB
testcase_18	AC	1,550 ms; 31,016 KB
testcase_19	AC	1,455 ms; 26,996 KB
testcase_20	AC	1,543 ms; 43,496 KB
testcase_21	AC	1,648 ms; 43,564 KB
testcase_22	AC	1,800 ms; 51,644 KB
testcase_23	AC	1,571 ms; 27,484 KB
testcase_24	AC	1,650 ms; 31,376 KB

ソースコード

#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;

// Copied from https://kokiymgch.hatenablog.com/entry/2018/03/21/174958

//e2i[edge] -> index of the edge
//tree index : [0, 1, ..., bc.size() - 1] -> component
//tree index : [bc.size(), bc.size() + 1, ..., bc.size() + art.size() - 1] -> articulation
//cmp[index of edge] -> index of the node of the contructed tree
//cmp_node[index of node] -> -1 if it's not articulation, otherwise index of the node of the constructed tree
struct BiconnectedComponentTree {
        vector<int> ord, low, art, cmp, cmp_node;
        vector<bool> used;
        vector<vector<int>> g, tree;
        vector<vector<pair<int, int>>> bc;
        vector<pair<int, int>> tmp;
        map<pair<int, int>, int> e2i;
        int n, m, k = 0;
        BiconnectedComponentTree(const vector<vector<int>> &g, const map<pair<int, int>, int> &e2i) : g(g), e2i(e2i) {
                n = g.size();
                m = e2i.size();
                cmp_node.resize(n, -1);
                cmp.resize(m, -1);
                ord.resize(n, -1);
                low.resize(n, -1);
                used.resize(n, false);
        }
        void dfs(int u, int prev) {
                used[u] = true;
                ord[u] = k ++;
                low[u] = ord[u];
                bool is_art = false;
                int cnt = 0;
                for (auto v : g[u]) if (v != prev) {
                        if (ord[v] < ord[u]) { 
                                tmp.emplace_back(min(u, v), max(u, v));
                        }
                        if (!used[v]) {
                                cnt ++;
                                dfs(v, u);
                                low[u] = min(low[u], low[v]);
                                if (prev != -1 && low[v] >= ord[u]) {
                                        is_art = true;
                                }
                                if (low[v] >= ord[u]) {
                                        bc.push_back({});
                                        while (true) {
                                                pair<int, int> e = tmp.back();
                                                bc.back().emplace_back(e);
                                                tmp.pop_back();
                                                if (min(u, v) == e.first && max(u, v) == e.second) {
                                                        break;
                                                }
                                        }
                                }
                        } else {
                                low[u] = min(low[u], ord[v]);
                        }
                }
                if (prev == -1 && cnt > 1) is_art = true;
                if (is_art) art.push_back(u);
        }
        void build() {
                dfs(0, -1);
                for (int i = 0; i < (int) bc.size(); i ++) {
                        for (auto e : bc[i]) {
                                cmp[e2i[make_pair(min(e.first, e.second), max(e.first, e.second))]] = i;
                        }
                }
                tree.resize(bc.size() + art.size());
                for (int i = 0; i < (int) art.size(); i ++) {
                        int j = i + (int) bc.size();
                        cmp_node[art[i]] = j;
                        int u = art[i];
                        set<int> tmp;
                        for (auto v : g[u]) {
                                int t = cmp[e2i[make_pair(min(u, v), max(u, v))]];
                                if (tmp.count(t) == 0) {
                                        tmp.insert(t);
                                }
                        }
                        for (auto v : tmp) {
                                tree[j].push_back(v);
                                tree[v].push_back(j);
                        }
                }
        }
};

/**
 * Lowest Common Ancestor. Call lca(x, y) to get the lca of them.
 * Header Requirement: vector, cassert
 * Verified by: AtCoder ABC014-D (http://abc014.contest.atcoder.jp/submissions/759125)
 */
class LowestCommonAncestor {
private:
  int n, bn;
  std::vector<int> parent; // 0 is root, parent[0] = 0
  std::vector<int> dep;
  
  // Lowest Common Ancestor
  
  std::vector<std::vector<int> > lca_tbl;
  
  void dfs(const std::vector<std::vector<int> > &edges, int v, int par, int d) {
    parent[v] = par;
    dep[v] = d;
    
    for (int i = 0; i < edges[v].size(); ++i) {
      int u = edges[v][i];
      if (u != par) {
	dfs(edges, u, v, d + 1);
      }
    }
  }
  
  void lca_init(void) {
    for (int v = 0; v < n; ++v) {
      lca_tbl[v] = std::vector<int>(bn + 1, 0);
      lca_tbl[v][0] = parent[v];
    }
    for (int i = 1; i <= bn; ++i) {
      for (int v = 0; v < n; ++v) {
	lca_tbl[v][i] = lca_tbl[lca_tbl[v][i - 1]][i - 1];
      }
    }
  }
public:
  int lca(int x, int y) const {
    int dx = dep[x];
    int dy = dep[y];
    if (dx > dy) {
      return lca(y, x);
    }
    // Go up from y to the depth of x
    for (int l = bn; l >= 0; --l) {
      if (dy - dx >= 1 << l) {
	y = lca_tbl[y][l];
	dy -= 1 << l;
      }
    }

    assert (dx == dy);

    if (x == y) {
      return x;
    }
  
    for (int l = bn; l >= 0; --l) {
      if (lca_tbl[x][l] != lca_tbl[y][l]) {
	x = lca_tbl[x][l];
	y = lca_tbl[y][l];
      }
    }
    return lca_tbl[x][0];
  }
  int depth(int a) const {
    return dep[a];
  }
  LowestCommonAncestor(int n, const std::vector<std::vector<int> > &edges)
    : n(n), parent(n), dep(n), lca_tbl(n) {
    bn = 0;
    while (n > 1 << bn) {
      bn++;
    }
    dfs(edges, 0, 0, 0);
    lca_init();
  }
};

void dfs(int v, int par, const vector<VI> &g, int d, VI &dep) {
  dep[v] = d;
  for (int w: g[v]) {
    if (w != par) dfs(w, v, g, d + 1, dep);
  }
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<VI> g(n);
  map<PI, int> e2i;
  REP(i, 0, m) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
    e2i[PI(min(u, v), max(u, v))] = i;
  }
  
  BiconnectedComponentTree bct(g, e2i);
  bct.build();
  if (0) {
  REP(i, 0, bct.cmp.size()) {
    cerr << i << ": " << bct.cmp[i] << endl;
  }
  REP(i, 0, n) {
    cerr << i << ": " << bct.cmp_node[i] << endl;
  }
  REP(i, 0, bct.tree.size()) {
    cerr << i << ":";
    for (int w: bct.tree[i]) cerr << " " << w;
    cerr << endl;
  }}
  VI dep(bct.tree.size());
  dfs(0, bct.tree.size(), bct.tree, 0, dep);
  for (int v: dep) cerr << " " << v;
  cerr << endl;
  LowestCommonAncestor lca(bct.tree.size(), bct.tree);
  int q;
  cin >> q;
  REP(_, 0, q) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    if (x == y) {
      cout << "0\n";
      continue;
    }
    int bx = bct.cmp_node[x];
    int by = bct.cmp_node[y];
    if (bx < 0) {
      int w = g[x][0];
      int e = e2i[PI(min(x, w), max(x, w))];
      bx = bct.cmp[e];
    }
    if (by < 0) {
      int w = g[y][0];
      int e = e2i[PI(min(y, w), max(y, w))];
      by = bct.cmp[e];
    }
    cerr << "bx = " << bx << " by = " << by << endl;
    int l = lca.lca(bx, by);
    int dist = dep[bx] + dep[by] - 2 * dep[l];
    cerr << "dist = " << dist << endl;
    if (bct.cmp_node[x] >= 0) {
      dist--;
    }
    if (bct.cmp_node[y] >= 0) {
      dist--;
    }
    cout << dist / 2 << "\n";
  }
}