結果

問題 No.1326 ふたりのDominator
コンテスト
ユーザー miscalc
提出日時 2025-09-12 11:48:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 332 ms / 2,000 ms
コード長 6,823 bytes
コンパイル時間 10,514 ms
コンパイル使用メモリ 294,892 KB
実行使用メモリ 33,948 KB
最終ジャッジ日時 2025-09-12 11:48:56
合計ジャッジ時間 15,395 ms
ジャッジサーバーID
（参考情報） 		judge / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
#define vc vector
using vl = vc<ll>;

#define ov(a, b, c, name, ...) name
#define rep2(i, l, r) for(ll i = (l); i < ll(r); i++)
#define rep1(i, n) rep2(i, 0, n)
#define rep(...) ov(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define fec(...) for(const auto& __VA_ARGS__)
#define per(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)

#define ALL(x) begin(x), end(x)
#define SZ(x) (ll) size(x)
#define LB(v, x) (lower_bound(ALL(v), x) - begin(v))
#define eb emplace_back

bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
const ll INF = ll(4e18) + 100;

void printvec(const auto& v) {
   for(auto it = begin(v); it != end(v); it++) cout << *it << " ";
   cout << endl;
}

#ifdef LOCAL
#define local(...) __VA_ARGS__
#else
#define local(...)
#endif

template<typename G> struct LL {
   int n;
   const G g;
   vc<int> ord, low, arti;
   vector<pll> bridge;

   LL(G g) : n(g.size()), g(g), ord(n, -1), low(n, -1) {
      int k = 0;
      rep(i, n) {
         if(ord[i] == -1) k = dfs(i, k, -1);
      }
   }

   int dfs(int x, int k, int p) {
      low[x] = ord[x] = k++;
      int cnt = 0;
      bool is_arti = false, second = false;
      fec(e : g[x]) {
         if(ord[e] == -1) {
            cnt++;
            k = dfs(e, k, x);
            chmin(low[x], low[e]);
            is_arti |= (p != -1) && (low[e] >= ord[x]);
            if(ord[x] < low[e]) bridge.eb(minmax<ll>(x, e));
         } else if(e != p or second) {
            chmin(low[x], ord[e]);
         } else {
            second = true;
         }
      }
      is_arti |= p == -1 && cnt > 1;
      if(is_arti) arti.eb(x);
      return k;
   }
};

// depends on lowlink
// 二重連結成分: 二重連結 (どの頂点を削除しても連結のまま) かつ極大な部分グラフ
// bc には辺集合が入る
// 辺はちょうど一つの bcc に属するが、頂点は複数の bcc に属することもある
// bc.size() は **孤立点以外の** bcc の個数
template<typename G> struct BCC : LL<G> {
   vc<bool> used;
   vc<vc<pll>> bc;
   vc<pll> tmp;
   using L = LL<G>;
   using L::g;
   using L::low;
   using L::ord;

   BCC(G g) : L(g) {
      used.assign(g.size(), 0);
      rep(i, used.size()) if(!used[i]) dfs(i, -1);
   }

   void dfs(int x, int p) {
      used[x] = true;
      fec(e : g[x]) {
         if(e == p) continue;
         if(!used[e] || ord[e] < ord[x]) tmp.eb(minmax<ll>(x, e));
         if(used[e]) continue;
         dfs(e, x);
         if(low[e] >= ord[x]) {
            bc.eb();
            while(true) {
               auto p = tmp.back();
               bc.back().eb(p);
               tmp.pop_back();
               if(p == (pll)minmax<ll>(x, e)) break;
            }
         }
      }
   }
};

// depends on lowlink, bcc
// 関節点 (an 個) と二重連結成分 (bn 個) からなる森 (tree に格納)
// 頂点番号は [0, an) と [an, an+bn)
// vtoi[v]: もとのグラフの頂点 v → BCT の頂点 i
// (関節点は関節点、それ以外は属する唯一の二重連結成分)
// 孤立点は -1 になるので注意
template <class G> struct BCT : BCC<G> {
   using B = BCC<G>;
   using B::bc;
   using B::L::arti;
   vc<vc<int>> tree;
   vc<int> vtoi;
   int an, bn;
   BCT(const G &g) : B(g) {
     an = arti.size(), bn = bc.size();
     tree.resize(an + bn);
     vtoi.resize(g.size(), -1);
     rep(i, an) vtoi[arti[i]] = i;
     rep(j, bn) fec([u, v] : bc[j]) fec(w : {u, v}) {
        int &i = vtoi[w];
        if(0 <= i && i < an) {
          if (tree[i].empty() || tree[i].back() != an + j) {
            tree[i].eb(an + j), tree[an + j].eb(i);
          }
        } else i = an + j;
     }
   }
};

template<class G> struct HLD {
   int n;
   G& g;
   vc<int> sub, in, out, head, rev, par, d;
   HLD(G& g, int root = 0) : n(g.size()), g(g), sub(n), in(n), out(n), head(n), rev(n), par(n), d(n) {
      int t = 0;
      head[root] = 0;
      dfs1(root, -1);
      dfs2(root, -1, t);
   }
   void dfs1(int x, int p) {
      par[x] = p;
      sub[x] = 1;
      if(g[x].size() and g[x][0] == p) swap(g[x][0], g[x].back());
      for(auto &e : g[x]) {
         if(e == p) continue;
         d[e] = d[x] + 1;
         dfs1(e, x);
         sub[x] += sub[e];
         if(sub[g[x][0]] < sub[e]) swap(g[x][0], e);
      }
   }
   void dfs2(int x, int p, int& t) {
      in[x] = t++;
      rev[in[x]] = x;
      fec(e : g[x]) {
         if(e == p) continue;
         head[e] = (g[x][0] == e ? head[x] : e);
         dfs2(e, x, t);
      }
      out[x] = t;
   }
   int la(int v, int k) {
      while(1) {
         int u = head[v];
         if(in[v] - k >= in[u]) return rev[in[v] - k];
         k -= in[v] - in[u] + 1;
         v = par[u];
      }
   }
   int lca(int u, int v) {
      for(;; v = par[head[v]]) {
         if(in[u] > in[v]) swap(u, v);
         if(head[u] == head[v]) return u;
      }
   }
   template<typename T, typename Q, typename F>
   T query(int u, int v, const T& e, const Q& q, const F& f, bool edge = false) {
      T l = e, r = e;
      for(;; v = par[head[v]]) {
         if(in[u] > in[v]) swap(u, v), swap(l, r);
         if(head[u] == head[v]) break;
         l = f(q(in[head[v]], in[v] + 1), l);
      }
      return f(f(q(in[u] + edge, in[v] + 1), l), r);
   }
   int dist(int u, int v) { return d[u] + d[v] - 2 * d[lca(u, v)]; }
   int jump(int s, int t, int i) {
      if(!i) return s;
      int l = lca(s, t);
      int dst = d[s] + d[t] - d[l] * 2;
      if(dst < i) return -1;
      if(d[s] - d[l] >= i) return la(s, i);
      i -= d[s] - d[l];
      return la(t, d[t] - d[l] - i);
   }
};

int main() {
   ll N, M;
   cin >> N >> M;
   vc<vl> G(N);
   rep(i, M) {
      ll u, v;
      cin >> u >> v;
      u--, v--;
      G.at(u).eb(v);
      G.at(v).eb(u);
   }
   BCT bct(G);
   auto& H = bct.tree;
   ll K = bct.an + bct.bn;
   local(rep(i, K) printvec(H.at(i)));
   local(printvec(bct.vtoi));
   HLD hld(H);
   vl dp(K);
   dp.at(0) = 0 < bct.an;
   queue<ll> que;
   que.push(0);
   while(!que.empty()) {
      ll v = que.front();
      que.pop();
      fec(c : H.at(v)) {
         if(hld.par.at(v) == c) continue;
         dp.at(c) = dp.at(v) + (c < bct.an);
         que.push(c);
      }
   }
   local(printvec(dp));

   ll Q;
   cin >> Q;
   rep(_, Q) {
      ll u, v;
      cin >> u >> v;
      u--, v--;
      if(u == v) {
         cout << 0 << "\n";
         continue;
      }
      ll i = bct.vtoi.at(u), j = bct.vtoi.at(v);
      ll k = hld.lca(i, j);
      local(cout << u << " " << v << "  " << i << " " << j << " " << k << endl);
      ll ans = dp.at(i) + dp.at(j) - dp.at(k) - (k == 0 ? 0 : dp.at(hld.par.at(k))) - (i < bct.an) - (j < bct.an);
      cout << ans << "\n";
   }
}
0