結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 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,940 KB
testcase_11 AC 3 ms
6,940 KB
testcase_12 AC 100 ms
19,160 KB
testcase_13 AC 100 ms
19,156 KB
testcase_14 AC 99 ms
19,160 KB
testcase_15 AC 96 ms
18,924 KB
testcase_16 AC 95 ms
18,548 KB
testcase_17 AC 93 ms
16,324 KB
testcase_18 AC 100 ms
14,380 KB
testcase_19 AC 82 ms
15,092 KB
testcase_20 AC 115 ms
21,524 KB
testcase_21 AC 127 ms
21,416 KB
testcase_22 AC 141 ms
22,720 KB
testcase_23 AC 79 ms
18,908 KB
testcase_24 AC 96 ms
19,160 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 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; 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