結果

問題 No.922 東北きりきざむたん
コンテスト
ユーザー arknave
提出日時 2019-11-08 22:17:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 112 ms / 2,000 ms
コード長 3,022 bytes
コンパイル時間 1,921 ms
コンパイル使用メモリ 172,944 KB
実行使用メモリ 25,856 KB
最終ジャッジ日時 2024-09-15 01:34:47
合計ジャッジ時間 4,721 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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