結果

問題 No.922 東北きりきざむたん
ユーザー QCFium
提出日時 2019-11-08 22:42:05
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 185 ms / 2,000 ms
コード長 2,518 bytes
コンパイル時間 2,342 ms
コンパイル使用メモリ 184,360 KB
実行使用メモリ 32,000 KB
最終ジャッジ日時 2024-09-15 01:54:12
合計ジャッジ時間 5,662 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
int ri() {
    int n;
    scanf("%d", &n);
    return n;
}
struct UnionFind {
    std::vector<int> data;
    UnionFind(int n) : data(n, -1) {}
    int root(int i) { return data[i] < 0 ? i : (data[i] = root(data[i])); }
    void unite(int i, int j) {
        i = root(i);
        j = root(j);
        if (i == j) return;
        if (data[i] > data[j]) std::swap(i, j);
        data[i] += data[j];
        data[j] = i;
    }
    bool same(int i, int j) { return root(i) == root(j); }
};
int n, m;
std::vector<std::vector<int> > hen, parent;
std::vector<bool> used;
std::vector<int> cnt, sum, depth;
void dfs1(int i, int prev, int d) {
    if (prev != -1) {
        parent[i].push_back(prev);
        int cur = prev;
        for (int k = 0; k < (int) parent[cur].size(); k++) {
            parent[i].push_back(cur = parent[cur][k]);
        }
    }
    depth[i] = d;
    used[i] = true;
    int cur = 0;
    for (auto j : hen[i]) {
        if (j == prev) continue;
        dfs1(j, i, d + 1);
        cur += sum[j];
    }
    sum[i] = cur + cnt[i];
}
int dfs2(int i, int prev, int over) {
    for (auto j : hen[i]) {
        if (j == prev) continue;
        if (sum[j] >= over) return dfs2(j, i, over);
    }
    return i;
}
int64_t dfs3(int i, int prev, int dist) {
    int64_t res = 0;
    for (auto j : hen[i]) if (j != prev) res += dfs3(j, i, dist + 1);
    return res + (int64_t) dist * cnt[i];
}
int lca(int i, int j) {
    if (i == j) return i;
    if (depth[i] > depth[j]) std::swap(i, j);
    int dif = depth[j] - depth[i];
    for (int i = 0; i < 20; i++) if (dif >> i & 1) j = parent[j][i];
    if (i == j) return i;
    for (int k = 20; k >= 0; k--) {
        if (k < (int) parent[i].size() and parent[i][k] != parent[j][k]) {
            i = parent[i][k];
            j = parent[j][k];
        }
    }
    return parent[i][0];
}
int main() {
    n = ri(), m = ri();
    int q = ri();
    hen.resize(n);
    used.resize(n);
    cnt.resize(n);
    sum.resize(n);
    depth.resize(n);
    parent.resize(n);
    UnionFind uni(n);
    for (int i = 0; i < m; i++) {
        int a = ri() - 1;
        int b = ri() - 1;
        hen[a].push_back(b);
        hen[b].push_back(a);
        uni.unite(a, b);
    }
    std::vector<std::pair<int, int> > sames;
    for (int i = 0; i < q; i++) {
        int a = ri() - 1, b = ri() - 1;
        if (uni.same(a, b)) {
            sames.push_back({a, b});
        } else {
            cnt[a]++;
            cnt[b]++;
        }
    }
    int64_t res = 0;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = true;
            dfs1(i, -1, 0);
            int root = dfs2(i, -1, (sum[i] + 1) / 2);
            res += dfs3(root, -1, 0);
        }
    }
    for (auto &i : sames) {
        int lc = lca(i.first, i.second);
        res += depth[i.first] + depth[i.second] - 2 * depth[lc];
    }
    std::cout << res << std::endl;
    
    
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0