結果

問題 No.1326 ふたりのDominator
ユーザー 👑 NachiaNachia
提出日時 2020-11-29 15:34:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 385 ms / 2,000 ms
コード長 3,006 bytes
コンパイル時間 2,625 ms
コンパイル使用メモリ 210,368 KB
最終ジャッジ日時 2025-01-16 10:08:45
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#define rep(i,n) for(int i=0;i<(n);i++)

struct rooted_tree{
private:
  int N;
  int logN;
  vector<vector<int>> E;
  int Root;
  vector<int> D;
  vector<vector<int>> P;
public:
  rooted_tree(int n){
    N=n;
    E.resize(n);
    logN=0; while(1<<logN < N) logN++;
  }
  int add_node(){
    int idx=N;
    E.push_back({});
    N++;
    while(1<<logN < N) logN++;
    return idx;
  }
  void add_edge(int parent,int child){
    E[parent].push_back(child);
  }
  void init_for_lca(int root){
    Root=root;
    P.resize(logN+1); rep(i,logN+1) P[i].resize(N);
    D.assign(N,-1); D[Root] = 0;
    queue<int> Q; Q.push(Root);
    while(Q.size()){
      int p=Q.front(); Q.pop();
      for(int e:E[p]){
        if(D[e]!=-1) continue;
        D[e]=D[p]+1;
        P[0][e]=p;
        Q.push(e);
      }
    }
    P[0][Root] = Root;
    rep(d,logN) rep(i,N) P[d+1][i] = P[d][P[d][i]];
  }
  int lca(int u,int v){
    if(D[u]<D[v]) swap(u,v);
    for(int d=logN; d>=0; d--) if(D[u] >= D[v]+(1<<d)) u=P[d][u];
    if(u==v) return u;
    for(int d=logN; d>=0; d--) if(P[d][u]!=P[d][v]){ u=P[d][u]; v=P[d][v]; }
    return P[0][u];
  }
  int distance(int u,int v){
    int g=lca(u,v);
    return D[u]+D[v]-D[g]*2;
  }
};

struct graph_original{
private:
  int N;
  vector<vector<int>> E;
  vector<int> dfsP;
  vector<int> dfsD;
  vector<int> condition_a;
  vector<int> dfsI;

private:
  int dfs1(int p){
    dfsI.push_back(p);
    int backedge = dfsD[p];
    for(int e:E[p]){
      if(dfsD[e]!=-1){
        backedge = min(backedge,dfsD[e]);
        continue;
      }
      dfsD[e] = dfsD[p]+1;
      dfsP[e] = p;
      int res = dfs1(e);
      if(res>=dfsD[p]) condition_a[e]=1;
      backedge = min(backedge,res);
    }
    return backedge;
  }
public:

  void construct_dfsTree(int root){
    dfsP.assign(N,-1);
    dfsD.assign(N,-1);
    condition_a.assign(N,0);
    dfsD[root] = 0;
    dfs1(root);
  }
public:
  graph_original(int n){
    N=n;
    E.resize(N);
  }
  void add_edge(int u,int v){
    E[u].push_back(v);
    E[v].push_back(u);
  }
  rooted_tree construct_tree(int root){
    rooted_tree res(N);
    construct_dfsTree(0);
    int p=-1;
    struct QueueNode { int v,p; };
    queue<QueueNode> Q; Q.push({0,-1});
    while(Q.size()){
      auto q = Q.front(); Q.pop();
      if(q.p != -1) res.add_edge(q.p,q.v);
      for(int e:E[q.v]){
        if(dfsD[e] != dfsD[q.v]+1) continue;
        QueueNode nx = {e,q.p};
        if(condition_a[e]){
          nx.p = res.add_node();
          res.add_edge(q.v,nx.p);
        }
        Q.push(nx);
      }
    }
    res.init_for_lca(root);
    return res;
  }
};

int main(){
  int N,M; cin>>N>>M;
  graph_original G(N);
  rep(i,M){ int u,v; cin>>u>>v; u--; v--; G.add_edge(u,v); }

  rooted_tree T = G.construct_tree(0);

  int Q; cin>>Q;
  rep(i,Q){
    int x,y; cin>>x>>y; x--; y--;
    int Dxy = T.distance(x,y);
    cout<<max(0,Dxy/2-1)<<endl;
  }

  return 0;
}
0