結果
問題 | No.1326 ふたりのDominator |
ユーザー |
![]() |
提出日時 | 2020-12-23 02:03:33 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 174 ms / 2,000 ms |
コード長 | 13,858 bytes |
コンパイル時間 | 16,499 ms |
コンパイル使用メモリ | 310,552 KB |
最終ジャッジ日時 | 2025-01-17 06:20:47 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 24 |
ソースコード
#ifdef ONLINE_JUDGE#pragma GCC target("avx2,avx")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#endif#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using i128 = __int128_t;using pii = pair<int, int>;using pll = pair<long long, long long>;template<class T> using vec = vector<T>;template<class T> using vvec = vector<vector<T>>;#define rep(i, n) for (int i = 0; i < (n); i++)#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)#define all(x) (x).begin(), (x).end()constexpr char ln = '\n';istream& operator>>(istream& is, __int128_t& x) {x = 0;string s;is >> s;int n = int(s.size()), it = 0;if (s[0] == '-') it++;for (; it < n; it++) x = (x * 10 + s[it] - '0');if (s[0] == '-') x = -x;return is;}ostream& operator<<(ostream& os, __int128_t x) {if (x == 0) return os << 0;if (x < 0) os << '-', x = -x;deque<int> deq;while (x) deq.emplace_front(x % 10), x /= 10;for (int e : deq) os << e;return os;}template<class T1, class T2>ostream& operator<<(ostream& os, const pair<T1, T2>& p) {return os << "(" << p.first << ", " << p.second << ")";}template<class T>ostream& operator<<(ostream& os, const vector<T>& v) {os << "{";for (int i = 0; i < int(v.size()); i++) {if (i) os << ", ";os << v[i];}return os << "}";}template<class Container> inline int SZ(Container& v) { return int(v.size()); }template<class T> inline void UNIQUE(vector<T>& v) { v.erase(unique(v.begin(), v.end()), v.end()); }template<class T1, class T2> inline bool chmax(T1& a, T2 b) { if (a < b) {a = b; return true ;} return false ;}template<class T1, class T2> inline bool chmin(T1& a, T2 b) { if (a > b) {a = b; return true ;} return false ;}inline int topbit(ull x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }inline int botbit(ull x) { return x == 0 ? 64 : __builtin_ctzll(x); }inline int popcount(ull x) { return __builtin_popcountll(x); }inline int kthbit(ull x, int k) { return (x>>k) & 1; }inline constexpr long long TEN(int x) { return x == 0 ? 1 : TEN(x-1) * 10; }inline void print() { cout << "\n"; }template<class T>inline void print(const vector<T>& v) {for (int i = 0; i < int(v.size()); i++) {if (i) cout << " ";cout << v[i];}print();}template<class T, class... Args>inline void print(const T& x, const Args& ... args) {cout << x << " ";print(args...);}#ifdef MINATO_LOCALinline void debug_out() { cerr << endl; }template <class T, class... Args>inline void debug_out(const T& x, const Args& ... args) {cerr << " " << x;debug_out(args...);}#define debug(...) cerr << __LINE__ << " : [" << #__VA_ARGS__ << "] =", debug_out(__VA_ARGS__)#define dump(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl#else#define debug(...) (void(0))#define dump(x) (void(0))#endifstruct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////struct UnionFind {int N;vector<int> node;UnionFind(){}UnionFind(int N) : N(N), node(N,-1) {}void init(int x) {node.assign(x,-1);N = x;}bool merge(int x, int y) {x = root(x); y = root(y);if (x == y) return false;if (node[x] > node[y]) swap(x,y);node[x] += node[y];node[y] = x;N--;return true;}bool same(int x, int y) {return root(x) == root(y);}int root(int x) {if (node[x] < 0) return x;return node[x] = root(node[x]);}int size(int x) {return -node[root(x)];}int count() const {return N;}};template<typename T>struct BinaryIndexedTree {int N;vector<T> data;BinaryIndexedTree(){}BinaryIndexedTree(int N) : N(N), data(N+1,0) {}// [0,k) (0-indexed) a[0] + … + a[k-1]T sum(int k) {T ret = 0;for(; k > 0; k -= k & -k) ret += data[k];return ret;}// [l,r) (0-indexed) a[l] + … + a[r-1]T sum(int l, int r) {if (l >= r) return 0;T vl = sum(l);T vr = sum(r);return vr - vl;}// (0-indexed) a[k] += x;void add(int k, T x) {for(++k; k <= N; k += k & -k) data[k] += x;}// (0-indexed)int lowerbound(T x) {int k = 1;int ret = 0;while ((k<<1) <= N) k <<= 1;while (k) {if (ret + k <= N && data[ret+k] < x) {x -= data[ret+k];ret += k;}k >>= 1;}return ret;}// (0-indexed)int upperbound(T x) {return lowerbound(x+1);}};/*辺は2つの頂点のうち深い方の頂点に対応させる(根は対応させない)!!辺クエリでも確保するセグ木の長さはN!(根に対応する添え字0だけ使わない)部分木クエリ 計算量 O(α) (セグ木ならO(logN))部分木頂点クエリseg.get(hld.vid[v],hld.vid[v]+hld.sub[v]);部分木辺クエリseg.get(hld.vid[v]+1,hld.vid[v]+hld.sub[v]);auto f=[&](int l, int r) {//区間[l,r)に対する処理};*/struct HeavyLightDecomposition {vector<vector<int>> G;vector<int> vid, head, sub, par, dep, inv, type;HeavyLightDecomposition(int N) :G(N),vid(N,-1),head(N),sub(N,1),par(N,-1),dep(N,0),inv(N),type(N){}void add_edge(int u,int v) {G[u].emplace_back(v);G[v].emplace_back(u);}void build(vector<int> rs = {0}) {int c = 0, pos = 0;for(int r : rs) {dfs_sz(r);head[r] = r;dfs_hld(r, c++, pos);}}void dfs_sz(int v) {for(int& u : G[v]) if(u==par[v]) swap(u,G[v].back());if(~par[v]) G[v].pop_back();for (int& u : G[v]) {par[u] = v;dep[u] = dep[v]+1;dfs_sz(u);sub[v] += sub[u];if(sub[u] > sub[G[v][0]]) swap(u,G[v][0]);}}void dfs_hld(int v, int c, int& pos) {vid[v] = pos++;inv[vid[v]] = v;type[v] = c;for(int u : G[v]) {if(u == par[v]) continue;head[u] = (u == G[v][0] ? head[v] : u);dfs_hld(u,c,pos);}}int lca(int u, int v) {while(true) {if(vid[u] > vid[v]) swap(u,v);if(head[u] == head[v]) return u;v = par[head[v]];}}int distance(int u, int v) {return dep[u] + dep[v] - 2*dep[lca(u,v)];}// for_each(vertex)template<class F>void for_each(int u, int v, const F& f) {while(true) {if(vid[u] > vid[v]) swap(u,v);f(max(vid[head[v]],vid[u]), vid[v]+1);if(head[u] != head[v]) v = par[head[v]];else break;}}template<class T, class Q, class F>T for_each(int u, int v, T ti, const Q& q, const F& f) {T l = ti, r = ti;while(true) {if(vid[u] > vid[v]) {swap(u,v);swap(l,r);}l = f(l, q(max(vid[head[v]],vid[u]), vid[v]+1));if(head[u] != head[v]) v = par[head[v]];else break;}return f(l,r);}// for_each(edge)// [l, r) <- attention!!template<class F>void for_each_edge(int u, int v, const F& f) {while(true) {if (vid[u] > vid[v]) swap(u,v);if (head[u] != head[v]) {f(vid[head[v]],vid[v]+1);v = par[head[v]];} else {if (u != v) f(vid[u]+1, vid[v]+1);break;}}}int search(int v, int d) {if (dep[v] < d || d < 0) return -1;while (true) {if (dep[v] - dep[head[v]] + 1 <= d) {d -= dep[v] - dep[head[v]] + 1;v = par[head[v]];} else {return inv[vid[v]-d];}}}};template< typename T = int >struct Edge {int from, to;T cost;int idx;Edge() = default;Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {}operator int() const { return to; }};template< typename T = int >struct Graph {vector< vector< Edge< T > > > g;int es;Graph() = default;explicit Graph(int n) : g(n), es(0) {}size_t size() const {return g.size();}void add_directed_edge(int from, int to, T cost = 1) {g[from].emplace_back(from, to, cost, es++);}void add_edge(int from, int to, T cost = 1) {g[from].emplace_back(from, to, cost, es);g[to].emplace_back(to, from, cost, es++);}void read(int M, int padding = -1, bool weighted = false, bool directed = false) {for(int i = 0; i < M; i++) {int a, b;cin >> a >> b;a += padding;b += padding;T c = T(1);if(weighted) cin >> c;if(directed) add_directed_edge(a, b, c);else add_edge(a, b, c);}}};template< typename T = int >using Edges = vector< Edge< T > >;template< typename T = int >struct LowLink : Graph< T > {public:using Graph< T >::Graph;vector< int > ord, low, articulation;vector< Edge< T > > bridge;using Graph< T >::g;virtual void build() {used.assign(g.size(), 0);ord.assign(g.size(), 0);low.assign(g.size(), 0);int k = 0;for(int i = 0; i < (int) g.size(); i++) {if(!used[i]) k = dfs(i, k, -1);}}explicit LowLink(const Graph< T > &g) : Graph< T >(g) {}private:vector< int > used;int dfs(int idx, int k, int par) {used[idx] = true;ord[idx] = k++;low[idx] = ord[idx];bool is_articulation = false, beet = false;int cnt = 0;for(auto &to : g[idx]) {if(to == par && !exchange(beet, true)) {continue;}if(!used[to]) {++cnt;k = dfs(to, k, idx);low[idx] = min(low[idx], low[to]);is_articulation |= par >= 0 && low[to] >= ord[idx];if(ord[idx] < low[to]) bridge.emplace_back(to);} else {low[idx] = min(low[idx], ord[to]);}}is_articulation |= par == -1 && cnt > 1;if(is_articulation) articulation.push_back(idx);return k;}};template< typename T = int >struct BiConnectedComponents : LowLink< T > {public:using LowLink< T >::LowLink;using LowLink< T >::g;using LowLink< T >::ord;using LowLink< T >::low;vector< vector< Edge< T > > > bc;void build() override {LowLink< T >::build();used.assign(g.size(), 0);for(int i = 0; i < used.size(); i++) {if(!used[i]) dfs(i, -1);}}explicit BiConnectedComponents(const Graph< T > &g) : Graph< T >(g) {}private:vector< int > used;vector< Edge< T > > tmp;void dfs(int idx, int par) {used[idx] = true;bool beet = false;for(auto &to : g[idx]) {if(to == par && !exchange(beet, true)) continue;if(!used[to] || ord[to] < ord[idx]) {tmp.emplace_back(to);}if(!used[to]) {dfs(to, idx);if(low[to] >= ord[idx]) {bc.emplace_back();for(;;) {auto e = tmp.back();bc.back().emplace_back(e);tmp.pop_back();if(e.idx == to.idx) break;}}}}}};template< typename T = int >struct BlockCutTree : BiConnectedComponents< T > {public:using BiConnectedComponents< T >::BiConnectedComponents;using BiConnectedComponents< T >::g;using BiConnectedComponents< T >::articulation;using BiConnectedComponents< T >::bc;vector< int > rev;vector< vector< int > > group;Graph< T > tree;explicit BlockCutTree(const Graph< T > &g) : Graph< T >(g) {}int operator[](const int &k) const {return rev[k];}void build() override {BiConnectedComponents< T >::build();rev.assign(g.size(), -1);int ptr = (int) bc.size();for(auto &idx : articulation) {rev[idx] = ptr++;}vector< int > last(ptr, -1);tree = Graph< T >(ptr);for(int i = 0; i < (int) bc.size(); i++) {for(auto &e : bc[i]) {for(auto &ver : {e.from, e.to}) {if(rev[ver] >= (int) bc.size()) {if(exchange(last[rev[ver]], i) != i) {tree.add_edge(rev[ver], i, e.cost);}} else {rev[ver] = i;}}}}group.resize(ptr);for(int i = 0; i < (int) g.size(); i++) {group[rev[i]].emplace_back(i);}}};int main() {int N,M; cin >> N >> M;BlockCutTree<> BCT(N);BCT.read(M);BCT.build();int K = BCT.tree.size();HeavyLightDecomposition HLD(K);UnionFind uf(K);rep(i,K) {for (auto& e : BCT.tree.g[i]) {if (uf.merge(e.from,e.to)) {HLD.add_edge(e.from,e.to);}}}HLD.build();BinaryIndexedTree<int> BIT(K);for (auto v : BCT.articulation) {BIT.add(HLD.vid[BCT[v]],1);}int Q; cin >> Q;while (Q--) {int x,y; cin >> x >> y;x--; y--;int u = BCT[x], v = BCT[y];if (u==v) {cout << 0 << ln;continue;}int ans = 0;auto f=[&](int l, int r) {ans += BIT.sum(l,r);return;};HLD.for_each(u,v,f);ans -= BIT.sum(HLD.vid[u],HLD.vid[u]+1);ans -= BIT.sum(HLD.vid[v],HLD.vid[v]+1);cout << ans << ln;}}