結果

問題 No.1326 ふたりのDominator
ユーザー drken1215drken1215
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
// Edge Class
template<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 class
template<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-link
template<class T> struct LowLink {
// results
vector<int> ord, low;
vector<int> aps; // articulation points
vector<Edge<T>> brs; // brideges
// constructor
LowLink() { }
LowLink(const Graph<T> &G) {
solve(G);
}
void init(const Graph<T> &G) {
solve(G);
}
// solver
int 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-tree
exist_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 {
// result
LowLink<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 results
vector<int> seen, finished;
vector<vector<pair<int, int>>> grouped_edges;
vector<pair<int, int>> tmp_edges;
// constructor
BiConnectedComponentsDecomposition() { }
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 graphv: 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 ap
else return ll.aps[v];
}
int get_size(int v) const { // including aps
if (v < (int)ll.aps.size()) return 1; // ap
else 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]}); // ap
else return groups[v - ll.aps.size()];
}
// solver
void 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 v
vector<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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0