結果
| 問題 | No.1326 ふたりのDominator |
| ユーザー |
 koba-e964
|
| 提出日時 | 2023-08-25 12:11:45 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,935 ms / 2,000 ms |
| コード長 | 7,924 bytes |
| コンパイル時間 | 2,334 ms |
| コンパイル使用メモリ | 156,180 KB |
| 最終ジャッジ日時 | 2025-02-16 13:27:22 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 24 |
ソースコード
#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 treestruct 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] = 0std::vector<int> dep;// Lowest Common Ancestorstd::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 xfor (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";}}