結果

問題 No.1326 ふたりのDominator
コンテスト
ユーザー Nachia
提出日時 2021-01-12 21:51:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 151 ms / 2,000 ms
コード長 3,349 bytes
コンパイル時間 3,642 ms
コンパイル使用メモリ 228,204 KB
最終ジャッジ日時 2025-01-17 16:53:18
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:150:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  150 |   int N,M; scanf("%d%d",&N,&M);
      |            ~~~~~^~~~~~~~~~~~~~
main.cpp:152:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  152 |   rep(i,M){ int u,v; scanf("%d%d",&u,&v); u--; v--; G.add_edge(u,v); }
      |                      ~~~~~^~~~~~~~~~~~~~
main.cpp:158:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  158 |     int x,y; scanf("%d%d",&x,&y); x--; y--;
      |              ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

#pragma GCC optimize ("Ofast")
#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