結果
問題 | No.1326 ふたりのDominator |
ユーザー |
|
提出日時 | 2022-12-12 01:04:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 175 ms / 2,000 ms |
コード長 | 10,027 bytes |
コンパイル時間 | 2,640 ms |
コンパイル使用メモリ | 216,844 KB |
最終ジャッジ日時 | 2025-02-09 09:51:38 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
#line 1 "test/graph/bcc/yuki1326.test.cpp"#define PROBLEM "https://yukicoder.me/problems/no/1326"#line 2 "src/Template.hpp"#define CUT#include <bits/stdc++.h>using namespace std;#define rep(i, l, r) for (int i = (l); i < (r); ++i)#define rrep(i, l, r) for (int i = (r); i --> (l);)#define all(c) begin(c), end(c)#ifdef LOCAL#define debug(...) debug_impl(#__VA_ARGS__, __VA_ARGS__)template <class H, class... Ts> void debug_impl(string s, H&& h, Ts&&... ts) {cerr << '(' << s << "): (" << forward<H>(h);((cerr << ", " << forward<Ts>(ts)), ..., (cerr << ")\n"));}#else#define debug(...) void(0)#endiftemplate <class T> bool chmax(T& a, const T& b) { return b > a ? (a = b, true) : false; }template <class T> bool chmin(T& a, const T& b) { return b < a ? (a = b, true) : false; }template <class T> istream& operator>>(istream& in, vector<T>& v) {for (auto& e : v) in >> e;return in;}template <class ...Args> void read(Args&... args) {(cin >> ... >> args);}template <class T> ostream& operator<<(ostream& out, const vector<T>& v) {int n = v.size();rep(i, 0, n) {out << v[i];if (i + 1 != n) out << ' ';}return out;}template <class H, class ...Ts> void print(H&& h, Ts &&... ts) {cout << h, ((cout << ' ' << forward<Ts>(ts)), ..., (cout << '\n'));}struct io_setup_ {io_setup_() {ios::sync_with_stdio(false), cin.tie(nullptr);cout << fixed << setprecision(10);}} io_setup{};#undef CUT#define NOTE compile command: \texttt{g++ -std=gnu++17 -Wall -Wextra -g -fsanitize=address -fsanitize=undefined \$\{file\} -o \$\{fileDirname\}/\$\{fileBasenameNoExtension\}}#undef NOTE#define NOTE \texttt{-DLOCAL} を加えると \texttt{debug(...)} による出力が有効となる#undef NOTE#line 3 "src/tree/HLD.hpp"#define CUTstruct HLD {int n;vector<int> visit, leave, head, ord, siz, par, dep;private:int dfs(vector<vector<int>>& g, int u, int p) {par[u] = p;int maxsiz = 0;for (int& v : g[u]) if (v != p) {dep[v] = dep[u] + 1;siz[u] += dfs(g, v, u);if (chmax(maxsiz, siz[v])) swap(g[u][0], v);}return siz[u];}int time = 0;void hld(const vector<vector<int>>& g, int u, int p) {visit[u] = time, ord[time] = u, ++time;head[u] = p >= 0 and g[p][0] == u ? head[p] : u;for (int v : g[u]) if (v != p) hld(g, v, u);leave[u] = time;}public:HLD() = default;HLD(vector<vector<int>>& g, vector<int> roots = {}):n(g.size()), visit(n), leave(n), head(n), ord(n), siz(n, 1), par(n, -1), dep(n) {for (int r : roots) if (par[r] < 0) dfs(g, r, -1);rep(r, 0, n) if (par[r] < 0) dfs(g, r, -1);rep(r, 0, n) if (par[r] < 0) hld(g, r, -1);}int size() const { return n; }int lca(int u, int v) const {for (;; v = par[head[v]]) {if (visit[u] > visit[v]) swap(u, v);if (head[u] == head[v]) return u;}}int la(int u, int k) const {if (k < 0) return -1;while (u >= 0) {int h = head[u];if (visit[u] - k >= visit[h]) return ord[visit[u] - k];k -= visit[u] - visit[h] + 1;u = par[h];}return -1;}int jump(int u, int v, int d) const {if (d < 0) return -1;int w = lca(u, v);int uw = dep[u] - dep[w];if (d <= uw) return la(u, d);int vw = dep[v] - dep[w];return d <= uw + vw ? la(v, (uw + vw) - d) : -1;}int dist(int u, int v) const {return dep[u] + dep[v] - 2 * dep[lca(u, v)];}vector<pair<int, int>> get_path(int u, int v, bool is_edge_query) const {vector<pair<int, int>> res;for (;; v = par[head[v]]) {if (visit[u] > visit[v]) swap(u, v);if (head[u] == head[v]) break;res.emplace_back(visit[head[v]], visit[v] + 1);}res.emplace_back(visit[u] + is_edge_query, visit[v] + 1);return res;}// uvパス上の値を順番通りに掛けた結果を返すtemplate <class T, class Op, class Prod, class RevProd>T fold_path_ordered(int u, int v, Op op, T e, Prod prod, RevProd rev_prod, bool is_edge_query) const {int w = lca(u, v);T sml = e, smr = e;for (auto [l, r] : get_path(u, w, is_edge_query)) sml = op(sml, rev_prod(l, r));for (auto [l, r] : get_path(v, w, true)) smr = op(prod(l, r), smr);return op(sml, smr);}pair<int, int> get_subtree(int u, bool is_edge_query) const {return { visit[u] + is_edge_query, leave[u] };}// vertex->idint get_id(int u) const {return visit[u];}// id->vertexのvectorvector<int> inv_ids() const {vector<int> inv(n);rep(i, 0, n) inv[visit[i]] = i;return inv;}vector<int> roots() const {vector<int> res;rep(i, 0, n) if (par[i] < 0) res.push_back(i);return res;}};#undef CUT#line 3 "src/graph/BCC.hpp"#define CUT#line 2 "src/graph/LowLink.hpp"#line 4 "src/graph/LowLink.hpp"#define CUTstruct LowLink {int n, m;vector<pair<int, int>> edges;vector<vector<pair<int, int>>> g;vector<int> ord, low, a_ids, b_ids;bool built = false;LowLink(const int n = 0): n(n), m(0), g(n), ord(n, -1), low(n) {}// Returns the id of the added edgeint add_edge(int u, int v) {built = false;edges.emplace_back(u, v);g[u].emplace_back(v, m);g[v].emplace_back(u, m);return m++;}void build() {if (exchange(built, true)) return;int t = 0;auto dfs = [&](auto dfs, int u, int id) -> void {bool is_root = id < 0, is_art = false;int cnt = 0;ord[u] = low[u] = t++;for (auto [v, id2] : g[u]) if (id != id2) {if (ord[v] < 0) {++cnt;dfs(dfs, v, id2);chmin(low[u], low[v]);if (ord[u] <= low[v]) {is_art = not is_root;if (ord[u] != low[v]) b_ids.push_back(id2);}} else {chmin(low[u], ord[v]);}}if (is_art or (is_root and cnt > 1)) {a_ids.push_back(u);}};rep(i, 0, n) if (ord[i] < 0) dfs(dfs, i, -1);}// Returns `\{i \mid \text{$e_i$ is a bridge} \}`const vector<int>& bridge_ids() {return build(), b_ids;}// Returns `\{i \mid \text{$v_i$ is an articulation point} \}`const vector<int>& articulation_points() {return build(), a_ids;}bool is_bridge(int u, int v) {build();if (ord[u] > ord[v]) swap(u, v);return ord[u] < low[v];}};#undef CUT#line 5 "src/graph/BCC.hpp"struct BCC {// isolated vertex <-> eid is emptyvector<int> vids, eids;};struct BCCDecomp: LowLink {// cid[i]: the id of BCC to which `e_i` belongsvector<int> cid;// isolated verticesvector<int> iso;BCCDecomp(int n = 0): LowLink(n) {}int build() {if (built) return iso.size() + (m ? *max_element(all(cid)) + 1 : 0);LowLink::build();vector<int8_t> used(n);int num = 0;cid.assign(m, -1);auto dfs = [&](auto dfs, int u, int peid) -> void {used[u] = true;static vector<int> edges;for (const auto& [v, eid] : g[u]) if (eid != peid) {if (not used[v] or ord[v] < ord[u]) edges.push_back(eid);if (used[v]) continue;dfs(dfs, v, eid);if (low[v] < ord[u]) continue;int e;do cid[e = edges.back()] = num, edges.pop_back(); while (e != eid);num++;}};for (int i = 0; i < n; ++i) if (not used[i]) {dfs(dfs, i, -1);if (g[i].empty()) iso.push_back(i);}return num + iso.size();}vector<BCC> bcc() {const int num = build(), vcmp = iso.size(), ecmp = num - vcmp;vector<BCC> res(num);rep(i, 0, m) {res[cid[i]].eids.push_back(i);}vector<int8_t> seen(n, false);rep(id, 0, ecmp) {for (int eid : res[id].eids) {const auto& [u, v] = edges[eid];if (not exchange(seen[u], true)) res[id].vids.push_back(u);if (not exchange(seen[v], true)) res[id].vids.push_back(v);}for (int v : res[id].vids) seen[v] = false;}rep(id, 0, vcmp) {res[ecmp + id].vids = { iso[id] };}return res;}// Let `C := \text{set of BCC}` and `A := \text{set of articulation points}`// Vertex set of BCT `V := C\sqcup A` (`0 \leq i < |C|` corresponds to the `i`-th BCC and `|C| \leq i < |C| + |A|` corresponds to the `(i-|C|)`-tharticulation point)// Edge set of BCT `E := \{(c, a) \in C\times A \mid a \in V(C) \}`vector<vector<int>> block_cut_tree(const vector<BCC> &bccs) {const int cnum = bccs.size(), anum = a_ids.size();vector<int> ids(n, -1);rep(i, 0, anum) {ids[a_ids[i]] = cnum + i;}vector<vector<int>> res(cnum + anum);rep(i, 0, cnum) {for (int v : bccs[i].vids) {if (int j = ids[v]; j >= 0) {res[i].push_back(j);res[j].push_back(i);}}}return res;}// Let `C := \text{set of BCC}` and `A := \text{the vertex set of original graph}`// Vertex set of BCT `V := C\sqcup A` (`0 \leq i < |C|` corresponds to the `i`-th BCC and `|C| \leq i < |C| + |A|` corresponds to the `(i-|C|)`-thvertex)// Edge set of BCT `E := \{(c, a) \in C\times A \mid a \in V(C) \}`vector<vector<int>> ext_block_cut_tree(const vector<BCC> &bccs) {const int cnum = bccs.size();vector<vector<int>> res(cnum + n);rep(i, 0, cnum) {for (int v : bccs[i].vids) {res[i].push_back(cnum + v);res[cnum + v].push_back(i);}}return res;}};#undef CUT#define NOTE 多重辺・自己ループがあってもよい#undef NOTE#line 5 "test/graph/bcc/yuki1326.test.cpp"int main() {int n, m;read(n, m);BCCDecomp bccd(n);rep(i, 0, m) {int u, v;read(u, v);--u, --v;bccd.add_edge(u, v);}auto bcc = bccd.bcc();auto bct = bccd.ext_block_cut_tree(bcc);HLD hld(bct);const int k = bcc.size();int q;read(q);rep(qid, 0, q) {int x, y;read(x, y);--x, --y;print(max(0, hld.dist(k + x, k + y) / 2 - 1));}}