結果

問題 No.922 東北きりきざむたん
ユーザー yakamotoyakamoto
提出日時 2019-11-08 22:35:33
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 6,227 bytes
コンパイル時間 2,014 ms
コンパイル使用メモリ 184,608 KB
実行使用メモリ 29,184 KB
最終ジャッジ日時 2024-09-15 01:45:23
合計ジャッジ時間 5,405 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 37 ms
13,096 KB
testcase_10 RE -
testcase_11 AC 33 ms
10,832 KB
testcase_12 AC 17 ms
13,888 KB
testcase_13 RE -
testcase_14 AC 54 ms
18,444 KB
testcase_15 AC 15 ms
14,636 KB
testcase_16 AC 100 ms
19,732 KB
testcase_17 AC 105 ms
19,728 KB
testcase_18 AC 101 ms
19,692 KB
testcase_19 AC 104 ms
19,732 KB
testcase_20 AC 98 ms
19,732 KB
testcase_21 AC 105 ms
20,224 KB
testcase_22 AC 127 ms
20,220 KB
testcase_23 AC 131 ms
19,580 KB
testcase_24 AC 126 ms
19,708 KB
testcase_25 AC 104 ms
20,372 KB
testcase_26 AC 101 ms
20,376 KB
testcase_27 AC 99 ms
20,368 KB
testcase_28 AC 34 ms
16,848 KB
testcase_29 AC 106 ms
29,184 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */


#ifndef SOLUTION_COMMON_H

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using PI = pair<int, int>;
template<class T> using V = vector<T>;
using VI = V<int>;
#define _1 first
#define _2 second

#ifdef MY_DEBUG
# define DEBUG(x) x
#else
# define DEBUG(x)
#endif

template<class A, class B>
std::ostream & operator <<(ostream &os, const pair<A, B> &p) {
  os << "(" << p._1 << "," << p._2 << ")";
  return os;
}

template<class T>
inline void debug(T &A) {
  DEBUG(
      for (const auto &a : A) {
        cerr << a << " ";
      }
      cerr << '\n';
  )
}

template<class T, class Func>
inline void debug_with_format(T &A, Func f) {
  DEBUG(
      for (const auto &a : A) {
        cerr << f(a) << " ";
      }
      cerr << '\n';
  )
}

template<class T>
inline void debug_dim2(T &A) {
  DEBUG(
      for (const auto &as : A) {
        debug(as);
      }
  )
}

template<typename ... Args>
inline void debug(const char *format, Args const &... args) {
  DEBUG(
      fprintf(stderr, format, args ...);
      cerr << '\n';
  )
}

template<typename ... Args>
string format(const string &fmt, Args ... args) {
  size_t len = snprintf(nullptr, 0, fmt.c_str(), args ...);
  vector<char> buf(len + 1);
  snprintf(&buf[0], len + 1, fmt.c_str(), args ...);
  return string(&buf[0], &buf[0] + len);
}

template<class T1, class T2>
string fmtP(pair<T1, T2> a) {
  stringstream ss;
  ss << "(" << a._1 << "," << a._2 << ")";
  return ss.str();
}

#define SOLUTION_COMMON_H

#endif //SOLUTION_COMMON_H


class UnionFind {
public:
  VI p;
  VI rank;

  UnionFind(int n): p(n), rank(n, 1) {
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
  }

  int unite(int x, int y) {
    int idx = find(x), idy = find(y);
    if (idx == idy) return idx;

    auto merge = [&](int nd, int rt) {
      rank[rt] += rank[nd];
      p[nd] = rt;
      return rt;
    };

    return rank[idx] < rank[idy] ? merge(idx, idy) : merge(idy, idx);
  }

  int find(int x) {
    return p[x] == x ? x : find(p[x]);
  }

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

  int count_connected(int x) {
    return rank[find(x)];
  }
};



class LCA {
public:
  int N;
  V<VI> anc;
  VI depth;
  int K;

  LCA(V<VI> &g, int K, VI& routes): N((int)g.size()), anc(K, VI(N)), depth(N), K(K) {
    function<void(int, int)> initParent = [&](int v, int p) {
      anc[0][v] = p;
      depth[v] = v == p ? 0 : depth[p] + 1;
      for (const auto &u : g[v]) {
        if (p != u) initParent(u, v);
      }
    };

    for (const auto &rt : routes) {
      initParent(rt, rt); // rtの親はrtってことにすると処理が楽になる
    }
    for (int k = 1; k < K; ++k) {
      for (int i = 0; i < N; ++i) {
        anc[k][i] = anc[k - 1][anc[k - 1][i]];
      }
    }
  }

  int get_anc(int v, int dist) {
    int i = 0;
    while(dist > 0) {
      if (dist >> i & 1) {
        dist -= 1 << i;
        v = anc[i][v];
      }
      i++;
    }
    return v;
  }

  int operator()(int v, int u) {
    int d = min(depth[v], depth[u]);
    v = get_anc(v, depth[v] - d);
    u = get_anc(u, depth[u] - d);
    if (v == u) return v;

    function<int(int, int, int)> dfs = [&](int v, int u, int s) {
      for (int k = s; k >= 0; --k) {
        if (anc[k][u] != anc[k][v]) {
          return dfs(anc[k][u], anc[k][v], k - 1);
        }
      }
      return anc[0][v];
    };

    return dfs(v, u, K - 1);
  }
};

const int MOD = 1000000007;

class C {
public:
  void solve(std::istream& in, std::ostream& out) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    in >> n >> m >> q;
    V<VI> g(n);
    UnionFind uf(n);

    for (int i = 0; i < m; ++i) {
      int u, v;
      in >> u >> v;
      u--; v--;
      g[u].push_back(v);
      g[v].push_back(u);
      uf.unite(u, v);
    }

    VI routes;
    V<bool> hoge(n);
    for (int i = 0; i < n; ++i) {
      if (!hoge[uf.find(i)]) {
        hoge[uf.find(i)] = true;
        routes.push_back(i);
      }
    }
    LCA lca(g, 20, routes);
    VI cnt(n);
    V<ll> sum(n);
    V<bool> visited(n);

    VI a(n), b(n);
    for (int i = 0; i < q; ++i) {
      in >> a[i] >> b[i];
      a[i]--; b[i]--;
    }

    function<void(int, int)> dfs = [&](int v, int p) {
      visited[v] = true;
      for (const auto &u : g[v]) {
        if (u != p) {
          dfs(u, v);
          cnt[v] += cnt[u];
          sum[v] += sum[u] + cnt[u];
        }
      }
    };

    ll ans = 0ll;

    // 連結成分内の計算
    for (int i = 0; i < q; ++i) {
      if (uf.same(a[i], b[i])) {
        int cp = lca(a[i], b[i]);
        int move = lca.depth[a[i]] + lca.depth[b[i]] - 2 * lca.depth[cp];
        ans += move;
      }
    }
    debug(routes);
    debug("ans:%lld", ans);

    auto calc1 = [&]() {
      fill(sum.begin(), sum.end(), 0);
      fill(visited.begin(), visited.end(), false);
      for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
          dfs(i, -1);
          ans += sum[i];
        }
      }

      debug(cnt);
      debug(sum);
      debug("ans:%lld", ans);
    };

    function<void(int, int, ll, int)> dfs2 = [&](int v, int p, ll total, int cntTotal) {
      visited[v] = true;
      if (p != -1) {
        int others = cntTotal - cnt[v];
        total += others - cnt[v];
        debug("v:%d cnt[v]:%d total:%d others:%d", v, cnt[v], total, others);
        ans = min(ans, total);
      }
      for (const auto &u : g[v]) {
        if (u != p) {
          dfs2(u, v, total, cntTotal);
        }
      }
    };

    auto calc2 = [&]() {
      fill(visited.begin(), visited.end(), false);
      for (int i = 0; i < n; ++i) {
        if (!visited[i]) dfs2(i, -1, ans, cnt[i]);
      }

      debug(cnt);
      debug(sum);
      debug("ans:%lld", ans);
    };

    // 連結成分をまたぐケースの計算
    fill(cnt.begin(), cnt.end(), 0);
    for (int i = 0; i < q; ++i) {
      if (!uf.same(a[i], b[i])) {
        cnt[a[i]]++; cnt[b[i]]++;
      }
    }
    calc1();
    calc2();

    out << ans;
  }
};


int main() {
	C solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}
0