#398023 (C++17) No.922 東北きりきざむたん

• 問題: No.922 東北きりきざむたん
• ユーザー: Haar
• 提出日時: 2019-11-14 02:27:57
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 229 ms / 2,000 ms
• コード長: 8,459 bytes
• コンパイル時間: 3,222 ms
• コンパイル使用メモリ: 235,892 KB
• 実行使用メモリ: 43,172 KB
• 最終ジャッジ日時: 2024-09-21 21:19:03
• 合計ジャッジ時間: 7,472 ms
• ジャッジサーバーID （参考情報）: judge1 / 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	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	3 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	3 ms; 5,376 KB
testcase_09	AC	83 ms; 22,952 KB
testcase_10	AC	33 ms; 8,064 KB
testcase_11	AC	64 ms; 17,312 KB
testcase_12	AC	68 ms; 32,864 KB
testcase_13	AC	24 ms; 10,496 KB
testcase_14	AC	135 ms; 36,676 KB
testcase_15	AC	64 ms; 36,256 KB
testcase_16	AC	166 ms; 30,888 KB
testcase_17	AC	167 ms; 31,008 KB
testcase_18	AC	167 ms; 31,136 KB
testcase_19	AC	168 ms; 31,012 KB
testcase_20	AC	172 ms; 31,008 KB
testcase_21	AC	172 ms; 29,552 KB
testcase_22	AC	174 ms; 29,540 KB
testcase_23	AC	222 ms; 32,756 KB
testcase_24	AC	229 ms; 32,884 KB
testcase_25	AC	172 ms; 33,068 KB
testcase_26	AC	181 ms; 33,060 KB
testcase_27	AC	180 ms; 33,064 KB
testcase_28	AC	116 ms; 43,172 KB
testcase_29	AC	228 ms; 35,692 KB

ソースコード

#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

struct Init{
  Init(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(12);
  }
}init;

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 ostream& operator<<(ostream &os, const Edge &e){
    os << "(FROM: " << e.from << "," << "TO: " << e.to << "," << "COST: " << e.cost << ")";
    return os;
  }
};

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

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

template <typename C, typename T> void add_undirected(C &g, int a, int b, T w){
  g[a].push_back(Edge<T>(a, b, w));
  g[b].push_back(Edge<T>(b, a, w));
}

class UnionFind{
  vector<int> parent, depth, size;
  int count;
public:
  UnionFind(){}
  UnionFind(int n): parent(n), depth(n,1), size(n,1), count(n){
    iota(ALL(parent),0);
  }
  int get_root(int i){
    if(parent[i] == i) return i;
    else return parent[i] = get_root(parent[i]);
  }
  bool is_same(int i, int j){return get_root(i) == get_root(j);}
  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;
      }
    }
  }
  int get_size(int i){return size[get_root(i)];}
  int count_group(){return count;}
};

template <typename T> class LCA{
private:
  vector<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:
  vector<int> depth;
  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 = vector<vector<int>>(n, vector<int>(log2n, 0));

    dfs(tree, root, -1, 0);
    REP(k,log2n-1){
      REP(v,n){
        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]) swap(a,b);
    REP(k,log2n) if((depth[b] - depth[a]) >> k & 1) b = parent[b][k];
    if(a == b) return a;
    REV(k, log2n-1, 0) 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(forward<F>(f)){}

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

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








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

  vector<int> tree_id;
  vector<int> vertex_id;

  vector<vector<int>> rid;

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

    for(auto &v : g){
      for(auto &e : v){
        uf.merge(e.from, e.to);
      }
    }

    int tree_num = uf.count_group();
    
    trees.resize(tree_num);

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

    rid.resize(tree_num);

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

    for(int i = 0; i < N; ++i){
      tree_id[i] = 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);
      }
    }
  }
  
  pair<int, int> forests_id(int i) const {
    return 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(cin >> N >> M >> Q){
    Graph<LLI> g(N);
    
    REP(i,M){
      int u, v; cin >> u >> v;
      --u, --v;
      add_undirected(g, u, v, 1LL);
    }

    LLI ans = 0;

    Forest<LLI> forest(g);

    int tree_num = forest.get_tree_num();
    vector<LCA<LLI>> lcas(tree_num);

    REP(i,tree_num){
      lcas[i] = LCA(forest.trees[i], 0);
    }


    vector<vector<int>> plans(tree_num);
    REP(i,tree_num){
      plans[i] = vector<int>(forest.trees[i].size());
    }
    
    REP(i,Q){
      int a,b; 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;
      }
    }


    dump(ans);

    REP(i,tree_num){
      const auto &tree = forest.trees[i];
      const auto &plan = plans[i];
      const int L = tree.size();

      vector<LLI> count(L);

      int s = 0;
      REP(i, L) if(plan[i]) s += plan[i];

      auto dfs =
        make_fix_point([&](auto &&f, int cur, int par) -> LLI{
                         LLI 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;
                       });


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

      //dump(dist, s, count);
      

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

                           LLI nd = d - count[e.to] + (s - count[e.to]);
                           chmin(t, nd);
                           
                           f(e.to, cur, nd);
                         }
                       });

      dfs2(0, -1, dist);

      ans += t;
    }

    cout << ans << endl;
  }

  return 0;
}