結果
問題 | No.922 東北きりきざむたん |
ユーザー | kimiyuki |
提出日時 | 2019-11-09 10:50:29 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 228 ms / 2,000 ms |
コード長 | 5,445 bytes |
コンパイル時間 | 2,892 ms |
コンパイル使用メモリ | 225,908 KB |
実行使用メモリ | 47,356 KB |
最終ジャッジ日時 | 2024-09-15 04:18:23 |
合計ジャッジ時間 | 7,731 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 3 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 | 80 ms
24,956 KB |
testcase_10 | AC | 56 ms
9,600 KB |
testcase_11 | AC | 76 ms
20,108 KB |
testcase_12 | AC | 48 ms
29,200 KB |
testcase_13 | AC | 25 ms
9,488 KB |
testcase_14 | AC | 126 ms
39,408 KB |
testcase_15 | AC | 40 ms
31,424 KB |
testcase_16 | AC | 205 ms
41,328 KB |
testcase_17 | AC | 205 ms
41,200 KB |
testcase_18 | AC | 200 ms
41,196 KB |
testcase_19 | AC | 202 ms
41,200 KB |
testcase_20 | AC | 201 ms
41,200 KB |
testcase_21 | AC | 226 ms
41,488 KB |
testcase_22 | AC | 228 ms
41,584 KB |
testcase_23 | AC | 213 ms
41,284 KB |
testcase_24 | AC | 215 ms
41,288 KB |
testcase_25 | AC | 194 ms
41,944 KB |
testcase_26 | AC | 197 ms
42,080 KB |
testcase_27 | AC | 196 ms
41,948 KB |
testcase_28 | AC | 109 ms
38,156 KB |
testcase_29 | AC | 207 ms
47,356 KB |
ソースコード
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) using namespace std; template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); } /** * @brief sparse table on a semilattice * @note a semilattice is a commutative idempotent semigroup * @note for convenience, it requires the unit * @note O(N log N) space */ template <class Semilattice> struct sparse_table { typedef typename Semilattice::value_type value_type; std::vector<std::vector<value_type> > table; Semilattice lat; sparse_table() = default; /** * @note O(N \log N) time */ sparse_table(std::vector<value_type> const & data, Semilattice const & a_lat = Semilattice()) : lat(a_lat) { int n = data.size(); int log_n = 32 - __builtin_clz(n); table.resize(log_n, std::vector<value_type>(n)); table[0] = data; REP (k, log_n - 1) { REP (i, n) { table[k + 1][i] = i + (1ll << k) < n ? lat.append(table[k][i], table[k][i + (1ll << k)]) : table[k][i]; } } } /** * @note O(1) */ value_type range_concat(int l, int r) const { if (l == r) return lat.unit(); // if there is no unit, remove this line assert (0 <= l and l < r and r <= table[0].size()); int k = 31 - __builtin_clz(r - l); // log2 return lat.append(table[k][l], table[k][r - (1ll << k)]); } }; struct indexed_min_semilattice { typedef std::pair<int, int> value_type; value_type unit() const { return { INT_MAX, INT_MAX }; } value_type append(value_type a, value_type b) const { return std::min(a, b); } }; /** * @brief lowest common ancestor with \pm 1 RMQ and sparse table * @see https://www.slideshare.net/yumainoue965/lca-and-rmq * @note verified http://www.utpc.jp/2011/problems/travel.html */ struct lowest_common_ancestor_for_forest { sparse_table<indexed_min_semilattice> table; std::vector<int> index; lowest_common_ancestor_for_forest() = default; /** * @note O(N) * @param g is an adjacent list of a tree */ lowest_common_ancestor_for_forest(std::vector<std::vector<int> > const & g) { std::vector<std::pair<int, int> > tour; index.assign(g.size(), -1); REP (root, g.size()) if (index[root] == -1) { dfs(root, -1, 0, g, tour); tour.emplace_back(-1, -1); } table = sparse_table<indexed_min_semilattice>(tour); } private: /** * @note to avoid stack overflow */ void dfs(int x, int parent, int depth, std::vector<std::vector<int> > const & g, std::vector<std::pair<int, int> > & tour) { index[x] = tour.size(); tour.emplace_back(depth, x); for (int y : g[x]) if (y != parent) { dfs(y, x, depth + 1, g, tour); tour.emplace_back(depth, x); } } public: /** * @note O(1) */ int operator () (int x, int y) const { assert (0 <= x and x < index.size()); assert (0 <= y and y < index.size()); x = index[x]; y = index[y]; if (x > y) std::swap(x, y); return table.range_concat(x, y + 1).second; } int get_depth(int x) const { assert (0 <= x and x < index.size()); return table.range_concat(index[x], index[x] + 1).first; } bool is_in_same_tree(int x, int y) const { return (*this)(x, y) != -1; } int get_dist(int x, int y) const { assert (0 <= x and x < index.size()); assert (0 <= y and y < index.size()); int z = (*this)(x, y); return get_depth(x) + get_depth(y) - 2 * get_depth(z); } }; int64_t solve(int n, int m, int q, const vector<vector<int> > & g, const vector<int> & a, const vector<int> & b) { lowest_common_ancestor_for_forest lca(g); int64_t answer = 0; vector<int> cnt(n); REP (i, q) { if (lca.is_in_same_tree(a[i], b[i])) { answer += lca.get_dist(a[i], b[i]); } else { ++ cnt[a[i]]; ++ cnt[b[i]]; } } vector<int64_t> imos(n); REP (root, n) if (lca.get_depth(root) == 0) { int sum_cnt = 0; function<int (int, int, int)> go1 = [&](int x, int parent, int depth) { sum_cnt += cnt[x]; imos[root] += depth * cnt[x]; int k = cnt[x]; for (int y : g[x]) if (y != parent) { k += go1(y, x, depth + 1); } if (x != root) { imos[x] += - 2 * k; } return k; }; go1(root, -1, 0); int64_t min_cost = INT64_MAX; function<void (int, int)> go2 = [&](int x, int parent) { chmin(min_cost, imos[x]); for (int y : g[x]) if (y != parent) { imos[y] += imos[x] + sum_cnt; go2(y, x); } }; go2(root, -1); answer += min_cost; } return answer; } int main() { int n, m, q; cin >> n >> m >> q; vector<vector<int> > g(n); REP (i, m) { int u, v; cin >> u >> v; -- u; -- v; g[u].push_back(v); g[v].push_back(u); } vector<int> a(q), b(q); REP (i, q) { cin >> a[i] >> b[i]; -- a[i]; -- b[i]; } cout << solve(n, m, q, g, a, b) << endl; return 0; }