結果

問題 No.922 東北きりきざむたん
ユーザー MayimgMayimg
提出日時 2019-11-10 19:43:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 170 ms / 2,000 ms
コード長 5,968 bytes
コンパイル時間 3,620 ms
コンパイル使用メモリ 225,376 KB
実行使用メモリ 43,088 KB
最終ジャッジ日時 2024-09-15 05:03:15
合計ジャッジ時間 7,311 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 59 ms
14,884 KB
testcase_10 AC 28 ms
6,400 KB
testcase_11 AC 51 ms
11,456 KB
testcase_12 AC 53 ms
20,108 KB
testcase_13 AC 19 ms
7,248 KB
testcase_14 AC 106 ms
22,948 KB
testcase_15 AC 51 ms
21,968 KB
testcase_16 AC 121 ms
21,600 KB
testcase_17 AC 121 ms
22,352 KB
testcase_18 AC 126 ms
20,864 KB
testcase_19 AC 128 ms
21,848 KB
testcase_20 AC 125 ms
21,848 KB
testcase_21 AC 118 ms
17,596 KB
testcase_22 AC 123 ms
17,312 KB
testcase_23 AC 151 ms
30,160 KB
testcase_24 AC 155 ms
30,740 KB
testcase_25 AC 125 ms
32,744 KB
testcase_26 AC 121 ms
32,740 KB
testcase_27 AC 126 ms
32,740 KB
testcase_28 AC 98 ms
25,896 KB
testcase_29 AC 170 ms
43,088 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
class UnionFind {
private:
  int siz;
  vector<int> a;

public:
  UnionFind(int x) : siz(x), a(x, -1) {}

  int root(int x) {
    return a[x] < 0 ? x : a[x] = root(a[x]);
  }

  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    siz--;
    if (a[x] > a[y]) swap(x, y);
    a[x] += a[y];
    a[y] =x;
    return true;
  }

  bool same(int x, int y) {
    return root(x) == root(y);
  }

  int size(int x) {
    return -a[root(x)];
  }
  
  int connected_component() {
  	return siz;
  }
};
class LowestCommonAncestor {
private:
  static const int MAX_SIZE = 30;
  vector<vector<int>> graph;
  vector<int> parent[MAX_SIZE];
  vector<int> depth;
  int bit_length;
  void copy(const vector<int> g[], int siz) { 
    graph.resize(siz);
    for (int i = 0; i < siz; ++i) for (int j : g[i]) graph[i].push_back(j);
  }
  void copy(const vector<vector<int>>& g, int siz = -1) {
    if (siz < 0) siz = (int) g.size();
    graph.resize(siz);
    for (int i = 0; i < siz; ++i) for (int j : g[i]) graph[i].push_back(j);
  }
  void initialize() {
    int siz = (int) graph.size();
    int root = 0;
    bit_length = 1;
    while ((1 << bit_length) < siz) ++bit_length;
    for (int i = 0; i < bit_length; ++i) parent[i].resize(siz);
    depth.assign(siz, -1);
    dfs(root, -1, 0);
    for (int i = 0; i < bit_length- 1; ++i) {
      for (int v = 0; v < siz; ++v) {
        if (depth[v] == -1) continue;
        if (parent[i][v] < 0) parent[i + 1][v] = -1;
        else parent[i + 1][v] = parent[i][parent[i][v]];
      }
    }
  }
  void dfs(int cur, int par, int d) {
    parent[0][cur] = par;
    depth[cur] = d;
    for (int child : graph[cur]) if (child != par) dfs(child, cur, d + 1);
  }
public:
  LowestCommonAncestor() {}
  LowestCommonAncestor(const vector<vector<int>>& g, int siz = -1) { build(g, siz); }
  LowestCommonAncestor(const vector<int> g[], int siz) { build(g, siz); }
  void build(const vector<int> g[], int siz) { copy(g, siz); initialize(); }
  void build(const vector<vector<int>>& g, int siz = -1) { copy(g, siz); initialize(); }
  int get(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int i = 0; i < bit_length; ++i) if (((depth[v] - depth[u]) >> i) & 1) v = parent[i][v];
    if (u == v) return u;
    for (int i = bit_length - 1; i >= 0; --i) if (parent[i][u] != parent[i][v]) u = parent[i][u], v = parent[i][v];
    return parent[0][u];
  }
};
using LCA = LowestCommonAncestor;

void dfs_depth (int cur, int par, vector<int>& depth, const vector<vector<int>>& g) {
  for (int child : g[cur]) if (child != par) {
    depth[child] = depth[cur] + 1;
    dfs_depth(child, cur, depth, g);
  }
}

void dfs1 (int cur, int par, vector<int>& num, vector<long long>& dp, const vector<int>& counts, const vector<vector<int>>& g) {
  num[cur] += counts[cur];
  for (int child : g[cur]) if (child != par) {
    dfs1(child, cur, num, dp, counts, g);
    num[cur] += num[child];
    dp[cur] += dp[child] + num[child];
  }
}

void dfs2 (int cur, int par, const vector<int>& num, const vector<long long>& dp, const vector<int>& counts, const vector<vector<int>>& g, long long x, long long y, long long& res) {
  res = min(res, dp[cur] + y);
  //cerr << cur << " " << dp[cur] << " " << x << endl;
  for (int child : g[cur]) if (child != par) {
    long long xx = num[cur] - num[child] + x;
    long long yy = dp[cur] - (dp[child] + num[child]) + y + xx;
    dfs2 (child, cur, num, dp, counts, g, xx, yy, res);
  }
}
long long calc (const vector<int>& counts, const vector<vector<int>>& g) {
  long long res = 1LL << 60;
  int siz = (int) counts.size();
  vector<int> num(siz);
  vector<long long> dp(siz);
  dfs1(0, -1, num, dp, counts, g);
  dfs2(0, -1, num, dp, counts, g, 0, 0, res);
  // cerr << "num = ";
  // for (int i : num) cerr << i << " ";
  // cerr << endl;
  // cerr << "dp = ";
  // for (long long i : dp) cerr << i << " ";
  // cerr << endl;
  return res;
}
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m, q;
  cin >> n >> m >> q;
  vector<vector<int>> g(n);
  UnionFind uf(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    g[u].push_back(v);
    g[v].push_back(u);
    uf.unite(u, v);
  }
  vector<int> in(n, -1), pos(n);
  vector<vector<int>> group;
  for (int i = 0; i < n; i++) {
    int r = uf.root(i);
    if (in[r] == -1) {
      in[r] = (int) group.size();
      group.push_back({});
    }
    in[i] = in[r];
    pos[i] = group[in[i]].size();
    group[in[i]].push_back(i);
  }
  int comp_siz = (int) group.size();
  vector<int> sizes(comp_siz);
  vector<vector<int>> comp_count(comp_siz);
  vector<vector<vector<int>>> comp_g(comp_siz);
  for (int i = 0; i < comp_siz; i++) {
    sizes[i] = (int) group[i].size();
    comp_count[i].resize(sizes[i]);
    comp_g[i].resize(sizes[i]);
  }
  for (int i = 0; i < n; i++) {
    for (int nbr : g[i]) {
      comp_g[in[i]][pos[i]].push_back(pos[nbr]);
    }
  }
  vector<vector<pair<int, int>>> query(comp_siz);
  for (int i = 0; i < q; i++) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    if (uf.same(a, b)) {
      query[in[a]].emplace_back(pos[a], pos[b]);
    } else {
      ++comp_count[in[a]][pos[a]];
      ++comp_count[in[b]][pos[b]];
    }
  }
  long long ans = 0;
  //cerr << comp_siz << endl;
  for (int i = 0; i < comp_siz; i++) {
    //long long dist_in = 0, dist_out = 0;
    LCA lca(comp_g[i]);
    vector<int> depth(sizes[i]);
    dfs_depth(0, -1, depth, comp_g[i]);
    ans += calc(comp_count[i], comp_g[i]);
    //dist_out += calc(comp_count[i], comp_g[i]);
    for (auto p : query[i]) {
      ans += depth[p.first] + depth[p.second] - depth[lca.get(p.first, p.second)] * 2;
      //dist_in += depth[p.first] + depth[p.second] - depth[lca.get(p.first, p.second)] * 2;
    }
    //cerr << i << " " << dist_in << " " << dist_out << endl;
  }
  cout << ans << '\n';
  return 0;
}
0