結果

問題 No.922 東北きりきざむたん
ユーザー HaarHaar
提出日時 2020-03-01 18:07:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 332 ms / 2,000 ms
コード長 7,293 bytes
コンパイル時間 3,642 ms
コンパイル使用メモリ 229,520 KB
実行使用メモリ 43,068 KB
最終ジャッジ日時 2024-04-21 22:20:48
合計ジャッジ時間 9,151 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 113 ms
23,056 KB
testcase_10 AC 61 ms
8,192 KB
testcase_11 AC 109 ms
17,284 KB
testcase_12 AC 71 ms
32,708 KB
testcase_13 AC 34 ms
10,624 KB
testcase_14 AC 185 ms
36,620 KB
testcase_15 AC 65 ms
36,412 KB
testcase_16 AC 265 ms
30,856 KB
testcase_17 AC 265 ms
31,108 KB
testcase_18 AC 266 ms
31,112 KB
testcase_19 AC 267 ms
31,232 KB
testcase_20 AC 271 ms
30,980 KB
testcase_21 AC 273 ms
29,776 KB
testcase_22 AC 271 ms
29,636 KB
testcase_23 AC 332 ms
32,856 KB
testcase_24 AC 329 ms
33,112 KB
testcase_25 AC 270 ms
33,036 KB
testcase_26 AC 269 ms
33,032 KB
testcase_27 AC 277 ms
33,156 KB
testcase_28 AC 164 ms
43,068 KB
testcase_29 AC 323 ms
35,664 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>


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){}

  Edge rev() const {return Edge(to,from,cost);}
  
  friend std::ostream& operator<<(std::ostream &os, const Edge &e){
    os << "(FROM: " << e.from << "," << "TO: " << e.to << "," << "COST: " << e.cost << ")";
    return os;
  }
};

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

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

template <typename C, typename T> void add_undirected(C &g, int a, int b, T w){
  add_edge(g, a, b, w);
  add_edge(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();
  }
};










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];
      const int L = tree.size();

      std::vector<int64_t> count(L);

      int s = 0;
      for(int i = 0; i < L; ++i) if(plan[i]) s += plan[i];

      auto dfs =
        make_fix_point([&](auto &&f, int cur, int par) -> int64_t {
                         int64_t ret = 0;

                         for(auto &e : tree[cur]){
                           if(e.to == par) continue;

                           ret += f(e.to, cur);

                           count[cur] += count[e.to];
                         }

                         ret += count[cur];

                         count[cur] += plan[cur];

                         return ret;
                       });


      int64_t dist = dfs(0, -1);
      int64_t t = dist;

      auto dfs2 =
        make_fix_point([&](auto &&f, int cur, int par, int64_t d) -> void{
                         for(auto &e : tree[cur]){
                           if(e.to == par) continue;

                           int64_t nd = d - count[e.to] + (s - count[e.to]);
                           t = std::min(t, nd);
                           
                           f(e.to, cur, nd);
                         }
                       });

      dfs2(0, -1, dist);

      ans += t;
    }
    
    std::cout << ans << std::endl;
  }

  return 0;
}
0