結果

問題 No.1326 ふたりのDominator
ユーザー 👑 NachiaNachia
提出日時 2020-11-29 15:34:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 342 ms / 2,000 ms
コード長 3,006 bytes
コンパイル時間 2,750 ms
コンパイル使用メモリ 219,832 KB
実行使用メモリ 22,476 KB
最終ジャッジ日時 2023-10-24 10:25:38
合計ジャッジ時間 9,292 ms
ジャッジサーバーID
(参考情報)
judge14 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 5 ms
4,348 KB
testcase_08 AC 4 ms
4,348 KB
testcase_09 AC 5 ms
4,348 KB
testcase_10 AC 4 ms
4,348 KB
testcase_11 AC 5 ms
4,348 KB
testcase_12 AC 271 ms
19,152 KB
testcase_13 AC 273 ms
19,152 KB
testcase_14 AC 279 ms
19,156 KB
testcase_15 AC 276 ms
18,916 KB
testcase_16 AC 280 ms
18,520 KB
testcase_17 AC 265 ms
16,604 KB
testcase_18 AC 291 ms
15,220 KB
testcase_19 AC 253 ms
15,948 KB
testcase_20 AC 294 ms
21,412 KB
testcase_21 AC 315 ms
21,432 KB
testcase_22 AC 342 ms
22,476 KB
testcase_23 AC 257 ms
18,888 KB
testcase_24 AC 274 ms
19,152 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; 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