結果

問題 No.1326 ふたりのDominator
ユーザー 👑 NachiaNachia
提出日時 2020-12-29 17:00:29
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 120 ms / 2,000 ms
コード長 3,318 bytes
コンパイル時間 2,731 ms
コンパイル使用メモリ 219,088 KB
実行使用メモリ 25,176 KB
最終ジャッジ日時 2024-09-23 03:04:00
合計ジャッジ時間 5,225 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 3 ms
6,944 KB
testcase_08 AC 3 ms
6,940 KB
testcase_09 AC 3 ms
6,944 KB
testcase_10 AC 3 ms
6,944 KB
testcase_11 AC 3 ms
6,948 KB
testcase_12 AC 107 ms
20,576 KB
testcase_13 AC 108 ms
20,448 KB
testcase_14 AC 110 ms
20,436 KB
testcase_15 AC 107 ms
20,384 KB
testcase_16 AC 110 ms
20,208 KB
testcase_17 AC 102 ms
18,944 KB
testcase_18 AC 105 ms
15,144 KB
testcase_19 AC 85 ms
15,864 KB
testcase_20 AC 95 ms
23,664 KB
testcase_21 AC 100 ms
23,816 KB
testcase_22 AC 120 ms
25,176 KB
testcase_23 AC 82 ms
20,500 KB
testcase_24 AC 106 ms
20,572 KB
権限があれば一括ダウンロードができます

ソースコード

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 LCA_RMQ{
  struct RMQ_Node{ int d,i; bool operator<(const RMQ_Node& r) const { return d<r.d; } };
  int N;
  vector<RMQ_Node> V;
  vector<int> R;
  void construct(){
    N=1; while(N<V.size()) N*=2;
    V.resize(N*2);
    rep(i,N) V[i+N]=V[i];
    for(int& r:R) r+=N;
    for(int i=N-1; i>=1; i--) V[i]=min(V[i*2],V[i*2+1]);
  }
  int lca(int u,int v){
    if(u==v) return u;
    int l=R[u], r=R[v];
    if(l>r) swap(l,r);
    r++;
    RMQ_Node ans=V[l];
    while(l<r){
      if(l&1) ans=min(ans,V[l++]);
      if(r&1) ans=min(ans,V[--r]);
      l/=2; r/=2;
    }
    return ans.i;
  }
};

struct rooted_tree{
private:
  int N;
  vector<vector<int>> E;
  int Root;
  vector<int> D;
  LCA_RMQ lca_rmq; 
  vector<int> P;
public:
  rooted_tree(int n){
    N=n;
    E.resize(n);
  }
  int add_node(){
    int idx=N;
    E.push_back({});
    N++;
    return idx;
  }
  void add_edge(int parent,int child){
    E[parent].push_back(child);
  }
  void dfs_lca(int p){
    lca_rmq.R[p]=lca_rmq.V.size();
    lca_rmq.V.push_back({D[p],p});
    for(int e:E[p]) if(P[p]!=e){
      P[e]=p;
      D[e]=D[p]+1;
      dfs_lca(e);
      lca_rmq.V.push_back({D[p],p});
    }
  }
  void init_for_lca(int root){
    Root=root;
    P.assign(N,-1);
    D.assign(N,-1); D[Root] = 0;
    lca_rmq.R.resize(N);
    dfs_lca(0);
    lca_rmq.construct();
  }
  int distance(int u,int v){
    int g=lca_rmq.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; };
    vector<QueueNode> Q; Q.push_back({0,-1});
    while(Q.size()){
      auto q = Q.back(); Q.pop_back();
      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_back(nx);
      }
    }
    res.init_for_lca(root);
    return res;
  }
};

int main(){
  int N,M; scanf("%d%d",&N,&M);
  graph_original G(N);
  rep(i,M){ int u,v; scanf("%d%d",&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; scanf("%d%d",&x,&y); x--; y--;
    int Dxy = T.distance(x,y);
    printf("%d\n",max(0,Dxy/2-1));
  }

  return 0;
}
0