結果

問題 No.922 東北きりきざむたん
ユーザー HaarHaar
提出日時 2020-05-17 07:48:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 339 ms / 2,000 ms
コード長 8,420 bytes
コンパイル時間 3,534 ms
コンパイル使用メモリ 245,752 KB
実行使用メモリ 69,516 KB
最終ジャッジ日時 2024-09-24 17:34:11
合計ジャッジ時間 9,853 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 3 ms
6,944 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 AC 3 ms
6,940 KB
testcase_09 AC 105 ms
23,056 KB
testcase_10 AC 63 ms
8,960 KB
testcase_11 AC 88 ms
17,692 KB
testcase_12 AC 76 ms
32,704 KB
testcase_13 AC 33 ms
10,624 KB
testcase_14 AC 163 ms
36,804 KB
testcase_15 AC 70 ms
36,392 KB
testcase_16 AC 252 ms
36,904 KB
testcase_17 AC 246 ms
38,024 KB
testcase_18 AC 240 ms
36,104 KB
testcase_19 AC 239 ms
37,384 KB
testcase_20 AC 253 ms
37,516 KB
testcase_21 AC 259 ms
31,156 KB
testcase_22 AC 263 ms
30,916 KB
testcase_23 AC 299 ms
51,432 KB
testcase_24 AC 293 ms
52,452 KB
testcase_25 AC 257 ms
53,524 KB
testcase_26 AC 263 ms
53,516 KB
testcase_27 AC 266 ms
53,544 KB
testcase_28 AC 147 ms
43,120 KB
testcase_29 AC 339 ms
69,516 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>


#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...)
#endif


template <typename Cost = int> class Edge{
public:
  int from,to;
  Cost cost;
  Edge() {}
  Edge(int to, Cost cost): to(to), cost(cost){}
  Edge(int from, int to, Cost cost): from(from), to(to), cost(cost){}
};

template <typename T> using Graph = std::vector<std::vector<Edge<T>>>;
template <typename T> using Tree = std::vector<std::vector<Edge<T>>>;

template <typename T, typename C> void add_edge(C &g, int from, int to, T w = 1){
  g[from].emplace_back(from, to, w);
}

template <typename T, typename C> void add_undirected(C &g, int a, int b, T w = 1){
  add_edge<T, C>(g, a, b, w);
  add_edge<T, C>(g, b, a, w);
}




class UnionFind{
  std::vector<int> parent, depth, size;
  int count;

public:
  UnionFind(int n): parent(n), depth(n,1), size(n,1), count(n){
    std::iota(parent.begin(), parent.end(), 0);
  }
  
  inline int get_root(int i){
    if(parent[i] == i) return i;
    else return parent[i] = get_root(parent[i]);
  }
  
  inline bool is_same(int i, int j){return get_root(i) == get_root(j);}

  inline int merge(int i, int j){
    int ri = get_root(i), rj = get_root(j);
    if(ri == rj) return ri;
    else{
      --count;
      if(depth[ri] < depth[rj]){
        parent[ri] = rj;
        size[rj] += size[ri];
        return rj;
      }else{
        parent[rj] = ri;
        size[ri] += size[rj];
        if(depth[ri] == depth[rj]) ++depth[ri];
        return ri;
      }
    }
  }

  inline int get_size(int i){return size[get_root(i)];}

  inline int count_group(){return count;}
};





template <typename T> class LCA{
private:
  std::vector<std::vector<int>> parent;
  int n, log2n;
  
  void dfs(const Tree<T> &tree, int cur, int par, int d){
    parent[cur][0] = par;
    depth[cur] = d;

    for(auto &e : tree[cur]){
      if(e.to != par){
        dist[e.to] = dist[cur] + e.cost;
        dfs(tree, e.to, cur, d+1);
      }
    }
  }
  
public:
  std::vector<int> depth;
  std::vector<T> dist;

  LCA(){}
  LCA(const Tree<T> &tree, int root):
    n(tree.size()), depth(n), dist(n)
  {
    log2n = (int)ceil(log(n) / log(2)) + 1;
    parent = std::vector<std::vector<int>>(n, std::vector<int>(log2n, 0));

    dfs(tree, root, -1, 0);
    for(int k = 0; k < log2n-1; ++k){
      for(int v = 0; v < n; ++v){
        if(parent[v][k] == -1) parent[v][k+1] = -1;
        else parent[v][k+1] = parent[parent[v][k]][k];
      }
    }
  }

  int query(int a, int b){
    if(depth[a] >= depth[b]) std::swap(a,b);
    for(int k = 0; k < log2n; ++k) if((depth[b] - depth[a]) >> k & 1) b = parent[b][k];
    if(a == b) return a;
    for(int k = log2n-1; k >= 0; --k) if(parent[a][k] != parent[b][k]){a = parent[a][k]; b = parent[b][k];}
    return parent[a][0];
  }

  T distance(int a, int b){
    return dist[a] + dist[b] - 2 * dist[query(a,b)];
  }
};



template <typename F>
struct FixPoint : F{
  explicit constexpr FixPoint(F &&f) noexcept : F(std::forward<F>(f)){}

  template <typename... Args>
  constexpr decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <typename F>
static inline constexpr decltype(auto) make_fix_point(F &&f){
  return FixPoint<F>(std::forward<F>(f));
}









template <typename T>
struct Forest{
  std::vector<Tree<T>> trees;

  std::vector<int> tree_id;
  std::vector<int> vertex_id;

  std::vector<std::vector<int>> rid;

  Forest(const Graph<T> &g){
    const int N = g.size();
    UnionFind uf(N);

    for(auto &v : g){
      for(auto &e : v){
        uf.merge(e.from, e.to);
      }
    }
    
    const int tree_num = uf.count_group();
    
    trees.resize(tree_num);

    tree_id.resize(N);
    vertex_id.resize(N);

    rid.resize(tree_num);

    std::vector<int> temp;
    for(int i = 0; i < N; ++i) temp.push_back(uf.get_root(i));
    std::sort(temp.begin(), temp.end());
    temp.erase(std::unique(temp.begin(), temp.end()), temp.end());

    for(int i = 0; i < N; ++i){
      tree_id[i] = std::lower_bound(temp.begin(), temp.end(), uf.get_root(i)) - temp.begin();
      vertex_id[i] = rid[tree_id[i]].size();
      rid[tree_id[i]].push_back(i);
    }

    for(int i = 0; i < tree_num; ++i){
      trees[i].resize(uf.get_size(temp[i]));
    }
    
    for(auto &v : g){
      for(auto &e : v){
        add_edge(trees[tree_id[e.from]], vertex_id[e.from], vertex_id[e.to], e.cost);
      }
    }
  }
  
  std::pair<int, int> forests_id(int i) const {
    return std::make_pair(tree_id[i], vertex_id[i]);
  }

  int original_id(int i, int j) const {
    return rid[i][j];
  }

  bool in_same_tree(int i, int j) const {
    return tree_id[i] == tree_id[j];
  }

  int get_tree_num() const {
    return trees.size();
  }
};



template <typename T, typename U, typename Merge, typename EdgeF, typename VertexF>
struct Rerooting{
  int N;
  T tree;
  U id;
  Merge merge;
  EdgeF f;
  VertexF g;
  
  std::vector<std::vector<U>> dp;
  std::vector<U> result;
  
  Rerooting(T tree, U id, Merge merge, EdgeF f, VertexF g):
    N(tree.size()), tree(tree), id(id), merge(merge), f(f), g(g), dp(N), result(N, id)
  {
    for(int i = 0; i < N; ++i) dp[i].assign((int)tree[i].size(), id);
    rec1(0);
    rec2(0, -1, id);
    for(int i = 0; i < N; ++i){
      for(int j = 0; j < (int)tree[i].size(); ++j){
        result[i] = merge(result[i], f(dp[i][j], tree[i][j]));
      }
      
      result[i] = g(result[i], i);
    }
  }

  U rec1(int cur, int par = -1){
    U acc = id;
    
    for(int i = 0; i < (int)tree[cur].size(); ++i){
      auto &e = tree[cur][i];
      if(e.to == par) continue;
      dp[cur][i] = rec1(e.to, cur);
      acc = merge(acc, f(dp[cur][i], e));
    }

    return g(acc, cur);
  }

  void rec2(int cur, int par, U value){
    const int l = tree[cur].size();

    for(int i = 0; i < l; ++i){
      if(tree[cur][i].to == par){
        dp[cur][i] = value;
      }
    }

    std::vector<U> left(l+1, id), right(l+1, id);

    for(int i = 0; i < l-1; ++i){
      const auto &e = tree[cur][i];
      left[i+1] = merge(left[i], f(dp[cur][i], e));
    }

    for(int i = l-1; i >= 1; --i){
      const auto &e = tree[cur][i];
      right[i-1] = merge(right[i], f(dp[cur][i], e));
    }

    for(int i = 0; i < l; ++i){
      const auto &e = tree[cur][i];
      if(e.to == par) continue;

      rec2(e.to, cur, g(merge(left[i], right[i]), cur));
    }
  }
};

template <typename T, typename G, typename Merge, typename EdgeF, typename VertexF>
auto make_rerooting(const G &tree, T id, Merge merge, EdgeF f, VertexF g){
  return Rerooting<G,T,Merge,EdgeF,VertexF>(tree, id, merge, f, g);
}








int main(){
  int N,M,Q;
  while(std::cin >> N >> M >> Q){
    Graph<int64_t> g(N);
    
    for(int i = 0; i < M; ++i){
      int u, v; std::cin >> u >> v;
      --u, --v;
      add_undirected(g, u, v, 1LL);
    }

    int64_t ans = 0;

    Forest<int64_t> forest(g);

    const int tree_num = forest.get_tree_num();
    std::vector<LCA<int64_t>> lcas(tree_num);

    for(int i = 0; i < tree_num; ++i){
      lcas[i] = LCA(forest.trees[i], 0);
    }

    std::vector<std::vector<int>> plans(tree_num);
    for(int i = 0; i < tree_num; ++i){
      plans[i] = std::vector<int>(forest.trees[i].size());
    }
    
    for(int i = 0; i < Q; ++i){
      int a,b; std::cin >> a >> b;
      --a, --b;

      if(forest.in_same_tree(a, b)){
        ans += lcas[forest.tree_id[a]].distance(forest.vertex_id[a], forest.vertex_id[b]);
      }else{
        plans[forest.tree_id[a]][forest.vertex_id[a]] += 1;
        plans[forest.tree_id[b]][forest.vertex_id[b]] += 1;
      }
    }

    for(int i = 0; i < tree_num; ++i){
      const auto &tree = forest.trees[i];
      const auto &plan = plans[i];

      auto res =
        make_rerooting<std::pair<int,int>>(
          tree,
          std::make_pair(0, 0),
          [](const auto &a, const auto &b){return std::make_pair(a.first + b.first, a.second + b.second);},
          [&](const auto &x, const auto &e){return std::make_pair(x.first, x.second + x.first);},
          [&](const auto &x, int v){return std::make_pair(x.first + plan[v], x.second);}
        ).result;
      
      ans +=
        std::min_element(
          res.begin(),
          res.end(),
          [](const auto &a, const auto &b){return a.second < b.second;}
        )->second;
    }
    
    std::cout << ans << std::endl;
  }

  return 0;
}
0