#596766 (C++17) No.1326 ふたりのDominator

• 問題: No.1326 ふたりのDominator
• ユーザー: milanis48663220
• 提出日時: 2020-12-23 13:16:53
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 7,626 bytes
• コンパイル時間: 865 ms
• コンパイル使用メモリ: 95,684 KB
• 最終ジャッジ日時: 2024-11-14 23:57:20
• 合計ジャッジ時間: 2,249 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

コンパイルメッセージ

main.cpp: In member function 'int LowLink<T>::dfs(int, int, int)':
main.cpp:98:24: error: there are no arguments to 'exchange' that depend on a template parameter, so a declaration of 'exchange' must be available [-fpermissive]
   98 |       if(to == par && !exchange(beet, true)) {
      |                        ^~~~~~~~
main.cpp:98:24: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
main.cpp: In member function 'void BiConnectedComponents<T>::dfs(int, int)':
main.cpp:145:24: error: there are no arguments to 'exchange' that depend on a template parameter, so a declaration of 'exchange' must be available [-fpermissive]
  145 |       if(to == par && !exchange(beet, true)) continue;
      |                        ^~~~~~~~
main.cpp: In instantiation of 'void BlockCutTree<T>::build() [with T = int]':
main.cpp:278:14:   required from here
main.cpp:196:24: error: 'exchange' was not declared in this scope
  196 |             if(exchange(last[rev[ver]], i) != i) {
      |                ~~~~~~~~^~~~~~~~~~~~~~~~~~~
main.cpp: In instantiation of 'void BiConnectedComponents<T>::dfs(int, int) [with T = int]':
main.cpp:131:20:   required from 'void BiConnectedComponents<T>::build() [with T = int]'
main.cpp:184:38:   required from 'void BlockCutTree<T>::build() [with T = int]'
main.cpp:278:14:   required from here
main.cpp:145:32: error: 'exchange' was not declared in this scope
  145 |       if(to == par && !exchange(beet, true)) continue;
      |                        ~~~~~~~~^~~~~~~~~~~~
main.cpp: In instantiation of 'int LowLink<T>::dfs(int, int, int) [with T = int]':
main.cpp:82:24:   required from 'void LowLink<T>::build() [with T = int]'
main.cpp:128:24:   required from 'void BiConnectedComponents<T>::build() [with T = int]'
main.cpp:184:38:   required from 'void BlockCutTree<T>::build() [with T = int]'
main.cpp:278:14:   required from here
main.cpp:98:32: error: 'exchange' was not declared in this scop

ソースコード

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cassert>

#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;
#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using namespace std;
typedef long long ll;

template< typename T >
struct Edge {
  int from, to;
  T cost;
  int idx;

  Edge() = default;

  Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {}

  operator int() const { return to; }
};

template< typename T = int >
struct Graph {
  vector< vector< Edge< T > > > g;
  int es;

  Graph() = default;

  explicit Graph(int n) : g(n), es(0) {}

  size_t size() const {
    return g.size();
  }

  void add_directed_edge(int from, int to, T cost = 1) {
    g[from].emplace_back((Edge< T >) {from, to, cost, es++});
  }

  void add_edge(int from, int to, T cost = 1) {
    g[from].emplace_back((Edge< T >) {from, to, cost, es});
    g[to].emplace_back((Edge< T >) {to, from, cost, es++});
  }

  void read(int M, int padding = -1, bool weighted = false, bool directed = false) {
    for(int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      a += padding;
      b += padding;
      T c = T(1);
      if(weighted) cin >> c;
      if(directed) add_directed_edge(a, b, c);
      else add_edge(a, b, c);
    }
  }
};

template< typename T = int >
struct LowLink : Graph< T > {
public:
  using Graph< T >::Graph;
  vector< int > ord, low, articulation;
  vector< Edge< T > > bridge;
  using Graph< T >::g;

  virtual void build() {
    used.assign(g.size(), 0);
    ord.assign(g.size(), 0);
    low.assign(g.size(), 0);
    int k = 0;
    for(int i = 0; i < (int) g.size(); i++) {
      if(!used[i]) k = dfs(i, k, -1);
    }
  }

  explicit LowLink(const Graph< T > &g) : Graph< T >(g) {}

private:
  vector< int > used;

  int dfs(int idx, int k, int par) {
    used[idx] = true;
    ord[idx] = k++;
    low[idx] = ord[idx];
    bool is_articulation = false, beet = false;
    int cnt = 0;
    for(auto &to : g[idx]) {
      if(to == par && !exchange(beet, true)) {
        continue;
      }
      if(!used[to]) {
        ++cnt;
        k = dfs(to, k, idx);
        low[idx] = min(low[idx], low[to]);
        is_articulation |= par >= 0 && low[to] >= ord[idx];
        if(ord[idx] < low[to]) bridge.emplace_back(to);
      } else {
        low[idx] = min(low[idx], ord[to]);
      }
    }
    is_articulation |= par == -1 && cnt > 1;
    if(is_articulation) articulation.push_back(idx);
    return k;
  }
};

template< typename T = int >
struct BiConnectedComponents : LowLink< T > {
public:
  using LowLink< T >::LowLink;
  using LowLink< T >::g;
  using LowLink< T >::ord;
  using LowLink< T >::low;

  vector< vector< Edge< T > > > bc;

  void build() override {
    LowLink< T >::build();
    used.assign(g.size(), 0);
    for(int i = 0; i < used.size(); i++) {
      if(!used[i]) dfs(i, -1);
    }
  }

  explicit BiConnectedComponents(const Graph< T > &g) : Graph< T >(g) {}

private:
  vector< int > used;
  vector< Edge< T > > tmp;

  void dfs(int idx, int par) {
    used[idx] = true;
    bool beet = false;
    for(auto &to : g[idx]) {
      if(to == par && !exchange(beet, true)) continue;
      if(!used[to] || ord[to] < ord[idx]) {
        tmp.emplace_back(to);
      }
      if(!used[to]) {
        dfs(to, idx);
        if(low[to] >= ord[idx]) {
          bc.emplace_back();
          for(;;) {
            auto e = tmp.back();
            bc.back().emplace_back(e);
            tmp.pop_back();
            if(e.idx == to.idx) break;
          }
        }
      }
    }
  }
};

template< typename T = int >
struct BlockCutTree : BiConnectedComponents< T > {
public:
  using BiConnectedComponents< T >::BiConnectedComponents;
  using BiConnectedComponents< T >::g;
  using BiConnectedComponents< T >::articulation;
  using BiConnectedComponents< T >::bc;

  vector< int > rev;
  vector< vector< int > > group;
  Graph< T > tree;

  explicit BlockCutTree(const Graph< T > &g) : Graph< T >(g) {}

  int operator[](const int &k) const {
    return rev[k];
  }

  void build() override {
    BiConnectedComponents< T >::build();
    rev.assign(g.size(), -1);
    int ptr = (int) bc.size();
    for(auto &idx : articulation) {
      rev[idx] = ptr++;
    }
    vector< int > last(ptr, -1);
    tree = Graph< T >(ptr);
    for(int i = 0; i < (int) bc.size(); i++) {
      for(auto &e : bc[i]) {
        for(auto &ver : {e.from, e.to}) {
          if(rev[ver] >= (int) bc.size()) {
            if(exchange(last[rev[ver]], i) != i) {
              tree.add_edge(rev[ver], i, e.cost);
            }
          } else {
            rev[ver] = i;
          }
        }
      }
    }
    group.resize(ptr);
    for(int i = 0; i < (int) g.size(); i++) {
      group[rev[i]].emplace_back(i);
    }
  }
};

class Lca{
    public:
        vector<int> depth;
        vector<vector<int>> parent;
        vector<vector<int>> G;
        int root;
        int n;
        const int N_LOG_MAX = 25;
        bool initialized = false;

        Lca(vector<vector<int>> g, int _root){
            n = g.size();
            G = g;
            root = _root;
            parent = vector<vector<int>>(N_LOG_MAX, vector<int>(n));
            depth = vector<int>(n, 0);
        }

        void init(){
            initialized = true;
            dfs(root, -1, 0);
            for(int i = 0; i < N_LOG_MAX-1; i++){
                for(int v = 0; v < n; v++){
                    if(parent[i][v] < 0) parent[i+1][v] = -1;
                    else parent[i+1][v] = parent[i][parent[i][v]];
                }
            }
        }

        int lca(int u, int v){
            assert(initialized);
            if(depth[u] > depth[v]) swap(u, v);
            for(int i = 0; i < N_LOG_MAX; i++){
                if((depth[v] - depth[u]) >> i & 1){
                    v = parent[i][v];
                }
            }
            if(u == v) return u;
            for(int i = N_LOG_MAX-1; i >= 0; i--){
                if(parent[i][u] != parent[i][v]) {
                    u = parent[i][u];
                    v = parent[i][v];
                }
            }
            return parent[0][u];
        }

    private:
        void dfs(int v, int p, int d){
            parent[0][v] = p;
            depth[v] = d;
            for(int i = 0; i < G[v].size(); i++){
                if(G[v][i] != p) dfs(G[v][i], v, d+1); 
            }
        }
};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int n, m;
    cin >> n >> m;
    BlockCutTree<> bct(n);
    bct.read(m);
    bct.build();
    vector<bool> is_articulation(n, false);

    for(int i : bct.articulation){
        is_articulation[i] = true;
    }
    vector<vector<int>> g(bct.tree.size());
    for(auto v : bct.tree.g){
        for(auto e : v){
            g[e.from].push_back(e.to);    
        }
    }
    Lca lca(g, 0);
    lca.init();
    int q; cin >> q;
    for(int i = 0; i < q; i++){
        int x, y; cin >> x >> y; x--; y--;
        int gx = bct.rev[x];
        int gy = bct.rev[y];
        int l = lca.lca(gx, gy);
        int dist = lca.depth[gx]+lca.depth[gy]-2*lca.depth[l];
        if(is_articulation[x]) dist--;
        if(is_articulation[y]) dist--;
        cout << max(0, dist/2) << endl;

    }
}