結果
問題 | No.1326 ふたりのDominator |
ユーザー |
![]() |
提出日時 | 2025-01-03 22:54:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 422 ms / 2,000 ms |
コード長 | 9,298 bytes |
コンパイル時間 | 2,859 ms |
コンパイル使用メモリ | 221,012 KB |
実行使用メモリ | 39,440 KB |
最終ジャッジ日時 | 2025-01-03 22:55:07 |
合計ジャッジ時間 | 9,484 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h>using namespace std;// Edge Classtemplate<class T> struct Edge {int from, to;T val;Edge() : from(-1), to(-1), val(-1) { }Edge(int f, int t, T v = -1) : from(f), to(t), val(v) {}friend ostream& operator << (ostream& s, const Edge& e) {return s << e.from << "->" << e.to;}};// graph classtemplate<class T> struct Graph {vector<vector<Edge<T>>> list;Graph() { }Graph(int n) : list(n) { }Graph(const Graph<T> &G) : list(G.list) { }void init(int n) {list.assign(n, vector<Edge<T>>());}Graph &operator = (const Graph &g) {list = g.list;return *this;}const vector<Edge<T>> &operator [] (int i) const { return list[i]; }const size_t size() const { return list.size(); }const void clear() {list.clear();}const void resize(int n) {list.resize(n);}void add_edge(int from, int to, T val = -1) {list[from].push_back(Edge(from, to, val));list[to].push_back(Edge(to, from, val));}friend ostream &operator << (ostream &s, const Graph &G) {s << endl;for (int i = 0; i < G.size(); ++i) {s << i << " -> ";for (const auto &e : G[i]) s << e.to << " ";s << endl;}return s;}};// low-linktemplate<class T> struct LowLink {// resultsvector<int> ord, low;vector<int> aps; // articulation pointsvector<Edge<T>> brs; // brideges// constructorLowLink() { }LowLink(const Graph<T> &G) {solve(G);}void init(const Graph<T> &G) {solve(G);}// solverint dfs(const Graph<T> &G, int t, int v, int p) {ord[v] = low[v] = t++;int num_of_children = 0;bool exist_articulation = false, is_multiple_edge = false;for (const auto &e : G[v]) {if (ord[e.to] == -1) {num_of_children++;t = dfs(G, t, e.to, v);low[v] = min(low[v], low[e.to]); // forward edge of DFS-treeexist_articulation |= (p != -1) && (low[e.to] >= ord[v]);if (ord[v] < low[e.to]) brs.push_back(e);} else if (e.to != p || is_multiple_edge) {low[v] = min(low[v], ord[e.to]); // back edge} else {is_multiple_edge = true;}}if (exist_articulation || (p == -1 && num_of_children > 1)) {aps.emplace_back(v);}return t;}void solve(const Graph<T> &G) {ord.assign(G.size(), -1), low.assign(G.size(), -1);for (int v = 0, k = 0; v < (int)G.size(); v++) {if (ord[v] == -1) k = dfs(G, k, v, -1);}}};// BiConnected Components decomposition// block-cut tree (aps: 0, 1, ..., A-1, components: A, A+1, ..., A+C-1)// (A: size of aps, C: num of components)template<class T> struct BiConnectedComponentsDecomposition {// resultLowLink<T> ll;vector<int> id_ap; // index of the articulation point (size: V)vector<int> id_cc; // index of the connected component (size: V)vector<vector<int>> groups; // biconnected components (size: C)vector<vector<int>> tree; // block-cut tree (size: A + C)// intermediate resultsvector<int> seen, finished;vector<vector<pair<int, int>>> grouped_edges;vector<pair<int, int>> tmp_edges;// constructorBiConnectedComponentsDecomposition() { }BiConnectedComponentsDecomposition(const Graph<T> &G) {solve(G);}void init(const Graph<T> &G) {solve(G);}// getter, original graph to block-cut tree (v: node of orignal graph)int is_ap_original_graph(int v) const {return (id_ap[v] != -1);}int get_id(int v) const {return (id_ap[v] == -1 ? id_cc[v] : id_ap[v]);}// getter, block-cut tree to orignal graph(v: node-id of block-cut tree)int is_ap(int v) const {return (v < ll.aps.size());}int get_ap(int v) const {if (v >= (int)ll.aps.size()) return -1; // not apelse return ll.aps[v];}int get_size(int v) const { // including apsif (v < (int)ll.aps.size()) return 1; // apelse return groups[v - ll.aps.size()].size();}vector<int> get_group(int v) const {if (v < (int)ll.aps.size()) return vector<int>({ll.aps[v]}); // apelse return groups[v - ll.aps.size()];}// solvervoid dfs(const Graph<T> &G, int v, int p) {seen[v] = true;if (G[v].empty()) {groups.emplace_back(vector<int>({v}));}for (const auto &e : G[v]) {if (e.to == p) continue;if (!seen[e.to] || ll.ord[e.to] < ll.ord[v]) {tmp_edges.emplace_back(minmax(v, e.to));}if (!seen[e.to]) {dfs(G, e.to, v);if (ll.low[e.to] >= ll.ord[v]) {groups.emplace_back(vector<int>({v}));grouped_edges.emplace_back();int ap = v;while (!tmp_edges.empty()) {const auto &e2 = tmp_edges.back();if (!finished[e2.first] && e2.first != ap) {groups.back().emplace_back(e2.first);finished[e2.first] = true;}if (!finished[e2.second] && e2.second != ap) {groups.back().emplace_back(e2.second);finished[e2.second] = true;}grouped_edges.back().emplace_back(e2);tmp_edges.pop_back();if (e2.first == min(v, e.to) && e2.second == max(v, e.to)) break;}}}}}void solve(const Graph<T> &G) {ll.init(G);seen.assign(G.size(), false), finished.assign(G.size(), false);for (int v = 0; v < (int)G.size(); v++) {if (!seen[v]) dfs(G, v, -1);}id_ap.assign(G.size(), -1), id_cc.assign(G.size(), -1);for (int i = 0; i < (int)ll.aps.size(); i++) {id_ap[ll.aps[i]] = i;}tree.assign(ll.aps.size() + grouped_edges.size(), vector<int>());vector<int> last(G.size(), -1);for (int i = 0; i < (int)grouped_edges.size(); i++) {vector<int> st;for (auto [u, v] : grouped_edges[i]) {st.push_back(u), st.push_back(v);}for (auto v : st) {if (id_ap[v] == -1) {id_cc[v] = i + ll.aps.size();} else if (last[v] != i) {tree[i + ll.aps.size()].push_back(id_ap[v]);tree[id_ap[v]].push_back(i + ll.aps.size());last[v] = i;}}}}};struct LCA {using Graph = vector<vector<int>>;vector<vector<int> > parent; // parent[d][v] := 2^d-th parent of vvector<int> depth;LCA() { }LCA(const Graph &G, int r = 0) { init(G, r); }void init(const Graph &G, int r = 0) {int V = (int)G.size();int h = 1;while ((1<<h) < V) ++h;parent.assign(h, vector<int>(V, -1));depth.assign(V, -1);dfs(G, r, -1, 0);for (int i = 0; i+1 < (int)parent.size(); ++i)for (int v = 0; v < V; ++v)if (parent[i][v] != -1)parent[i+1][v] = parent[i][parent[i][v]];}void dfs(const Graph &G, int v, int p, int d) {parent[0][v] = p;depth[v] = d;for (auto e : G[v]) if (e != p) dfs(G, e, v, d+1);}int get(int u, int v) {if (depth[u] > depth[v]) swap(u, v);for (int i = 0; i < (int)parent.size(); ++i)if ( (depth[v] - depth[u]) & (1<<i) )v = parent[i][v];if (u == v) return u;for (int i = (int)parent.size()-1; i >= 0; --i) {if (parent[i][u] != parent[i][v]) {u = parent[i][u];v = parent[i][v];}}return parent[0][u];}};int main() {int N, M, Q, u, v, x, y;cin >> N >> M;Graph<int> G(N);for (int i = 0; i < M; i++) {cin >> u >> v, u--, v--;G.add_edge(u, v);}BiConnectedComponentsDecomposition<int> bcc(G);auto tree = bcc.tree;LCA lca(tree);cin >> Q;while (Q--) {cin >> x >> y, x--, y--;int xid = bcc.get_id(x), yid = bcc.get_id(y);int l = lca.get(xid, yid);int len = lca.depth[xid] + lca.depth[yid] - lca.depth[l] * 2;int apnum = 0, res = 0;if (bcc.is_ap_original_graph(x)) apnum++;if (bcc.is_ap_original_graph(y)) apnum++;if (apnum == 0) res = len / 2;else if (apnum == 1) res = (len - 1) / 2;else res = len / 2 - 1;res = max(res, 0);cout << res << endl;//cout << x << ", " << y << ":: " << xid << ", " << yid << ": " << len << endl;}}