結果

問題 No.922 東北きりきざむたん
ユーザー arknavearknave
提出日時 2019-11-08 22:17:26
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 102 ms / 2,000 ms
コード長 3,022 bytes
コンパイル時間 1,534 ms
コンパイル使用メモリ 170,704 KB
実行使用メモリ 24,376 KB
最終ジャッジ日時 2023-10-13 03:57:41
合計ジャッジ時間 4,306 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
13,780 KB
testcase_01 AC 5 ms
13,872 KB
testcase_02 AC 5 ms
13,744 KB
testcase_03 AC 5 ms
13,844 KB
testcase_04 AC 5 ms
13,764 KB
testcase_05 AC 4 ms
13,840 KB
testcase_06 AC 5 ms
13,804 KB
testcase_07 AC 5 ms
13,816 KB
testcase_08 AC 5 ms
13,884 KB
testcase_09 AC 32 ms
16,812 KB
testcase_10 AC 23 ms
14,968 KB
testcase_11 AC 30 ms
16,116 KB
testcase_12 AC 17 ms
16,216 KB
testcase_13 AC 12 ms
14,588 KB
testcase_14 AC 48 ms
18,160 KB
testcase_15 AC 14 ms
16,384 KB
testcase_16 AC 83 ms
19,008 KB
testcase_17 AC 84 ms
19,064 KB
testcase_18 AC 84 ms
19,056 KB
testcase_19 AC 83 ms
18,904 KB
testcase_20 AC 81 ms
18,968 KB
testcase_21 AC 90 ms
19,252 KB
testcase_22 AC 96 ms
19,116 KB
testcase_23 AC 96 ms
18,980 KB
testcase_24 AC 102 ms
19,024 KB
testcase_25 AC 81 ms
19,736 KB
testcase_26 AC 80 ms
19,636 KB
testcase_27 AC 80 ms
19,636 KB
testcase_28 AC 32 ms
16,896 KB
testcase_29 AC 94 ms
24,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

constexpr int LOGN  = 18;
constexpr int MAXN = 1e5 + 5;
int n, m, q;
vi tree[MAXN];
int comp[MAXN];
int depth[MAXN];
int st[LOGN][MAXN];

ll tokens[MAXN];
ll sub_cost[MAXN];
ll dp[MAXN];

int lca(int u, int v) {
    assert(comp[u] == comp[v]);
    if (depth[u] > depth[v])
        swap(u, v);
    for (int j = LOGN - 1; j >= 0; --j) {
        if ((depth[v] - depth[u]) & (1 << j)) {
            v = st[j][v];
        }
    }

    if (u == v)
        return u;

    for (int j = LOGN - 1; j >= 0; --j) {
        if (st[j][u] != st[j][v]) {
            u = st[j][u];
            v = st[j][v];
        }
    }

    return st[0][u];
}

int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

void dfs1(int u, int p, int r) {
    comp[u] = r;
    for (int v : tree[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        st[0][v] = u;
        dfs1(v, u, r);
    }
}

void dfs2(int u, int p) {
    sub_cost[u] = 0;
    for (int v : tree[u]) {
        if (v == p) continue;

        dfs2(v, u);
        tokens[u] += tokens[v];
        sub_cost[u] += sub_cost[v] + tokens[v];
    }
}

void dfs3(int u, int p, ll cost) {
    dp[u] = cost;
    for (int v : tree[u]) {
        if (v == p) continue;

        ll new_cost = cost + tokens[comp[u]] - 2 * tokens[v];
        dfs3(v, u, new_cost);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    // Given a forest and a bunch of travel plans
    // If travel within a CC, fixed contribution
    // Otherwise, do some kind of DFS to get APSP? Tree re-rooting trick?
    // Take min on each component

    cin >> n >> m >> q;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    memset(st, -1, sizeof(st));
    vi roots;
    for (int i = 0; i < n; ++i) {
        if (depth[i] == 0) {
            roots.push_back(i);
            dfs1(i, -1, i);
        }
    }

    for (int j = 0; j + 1 < LOGN; ++j) {
        for (int u = 0; u < n; ++u) {
            if (st[j][u] != -1) {
                st[j + 1][u] = st[j][st[j][u]];
            }
        }
    }

    ll ans = 0;
    while (q-- > 0) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        if (comp[a] == comp[b]) {
            ans += dist(a, b);
        } else {
            ++tokens[a];
            ++tokens[b];
        }
    }

    for (int root : roots) {
        dfs2(root, -1);
        dfs3(root, -1, sub_cost[root]);
    }

    constexpr ll INF = 1e18;
    vector<ll> res(roots.size(), INF);
    for (int i = 0; i < n; ++i) {
        int idx = lower_bound(all(roots), comp[i]) - begin(roots);
        res[idx] = min(res[idx], dp[i]);
    }

    for (ll v : res) {
        ans += v;
    }

    cout << ans << '\n';

    return 0;
}
0