結果

問題 No.922 東北きりきざむたん
ユーザー aa
提出日時 2019-11-09 02:26:20
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 345 ms / 2,000 ms
コード長 5,862 bytes
コンパイル時間 2,329 ms
コンパイル使用メモリ 192,692 KB
実行使用メモリ 65,440 KB
最終ジャッジ日時 2024-09-15 03:53:28
合計ジャッジ時間 8,252 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 99 ms
24,956 KB
testcase_10 AC 62 ms
10,112 KB
testcase_11 AC 92 ms
20,692 KB
testcase_12 AC 36 ms
22,756 KB
testcase_13 AC 22 ms
8,448 KB
testcase_14 AC 139 ms
35,908 KB
testcase_15 AC 28 ms
23,828 KB
testcase_16 AC 279 ms
45,240 KB
testcase_17 AC 286 ms
45,240 KB
testcase_18 AC 272 ms
45,240 KB
testcase_19 AC 282 ms
45,116 KB
testcase_20 AC 278 ms
45,108 KB
testcase_21 AC 322 ms
47,384 KB
testcase_22 AC 317 ms
47,256 KB
testcase_23 AC 330 ms
46,748 KB
testcase_24 AC 327 ms
46,744 KB
testcase_25 AC 328 ms
47,672 KB
testcase_26 AC 323 ms
47,748 KB
testcase_27 AC 345 ms
47,796 KB
testcase_28 AC 89 ms
27,828 KB
testcase_29 AC 292 ms
65,440 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#define _GLIBCXX_DEBUG
#include "bits/stdc++.h"

using namespace std;

//------------------------------- Libraries --------------------------------//

class UnionFind
{
    vector<int> par;

public:
    UnionFind(int n) : par(n, -1) {}

    int root(int x)
    {
        if (par[x] < 0)
            return x;
        else
            return par[x] = root(par[x]);
    }

    inline bool same(int u, int v)
    {
        return root(u) == root(v);
    }

    bool merge(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        if (par[x] > par[y])
            swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) { return -par[root(x)]; }
};

class LowestCommonAncestor
{
    //2^k >= n
    int n, k;
    vector<vector<int>> g, par;
    vector<int> dis;

    inline void build()
    {
        for (int i = 0; i < n; i++)
        {
            if (dis[i] == -1)
            {
                dis[i] = 0;
                this->calc(i);
            }
        }
        this->setpar();
    }

    void calc(int v = 0, int p = -1)
    {
        this->par[0][v] = p;
        for (int nv : this->g[v])
        {
            if (nv != p)
            {
                this->dis[nv] = this->dis[v] + 1;
                this->calc(nv, v);
            }
        }
    }

    void setpar()
    {
        for (int i = 0; i < this->k; i++)
        {
            for (int v = 0; v < this->n; v++)
            {
                if (this->par[i][v] != -1)
                {
                    this->par[i + 1][v] = this->par[i][par[i][v]];
                }
            }
        }
    }

public:
    LowestCommonAncestor(int n_, vector<vector<int>> &g_) : n(n_), g(g_), dis(n, -1)
    {
        k = log2(n + 1);
        this->par.assign(k + 1, vector<int>(n, -1));
        this->build();
    }

    int get(int u, int v)
    {
        //dis[u] <= dis[v]
        if (this->dis[u] > this->dis[v])
        {
            swap(u, v);
        }
        int d = this->dis[v] - this->dis[u];
        for (int i = k; i >= 0; i--)
        {
            if (d >> i & 1)
            {
                v = this->par[i][v];
            }
        }
        if (u == v)
        {
            return v;
        }
        for (int i = k; i >= 0; i--)
        {
            if (this->par[i][u] != this->par[i][v])
            {
                u = this->par[i][u];
                v = this->par[i][v];
            }
        }
        return this->par[0][v];
    }

    int dist(int u, int v)
    {
        return this->dis[u] + this->dis[v] - 2 * dis[this->get(u, v)];
    }
};

//verified @ https://onlinejudge.u-aizu.ac.jp/status/users/sifi_border/submissions/1/GRL_5_C/judge/3883181/C++14
//verified @ https://atcoder.jp/contests/abc014/submissions/7617701

//------------------------------- Type Names -------------------------------//

using i64 = int_fast64_t;

using seika = string;
//akari : 1D, yukari : 2D, maki : 3D vector
template <class kizuna>
using akari = vector<kizuna>;
template <class yuzuki>
using yukari = akari<akari<yuzuki>>;
template <class tsurumaki>
using maki = akari<yukari<tsurumaki>>;
//akane : ascending order, aoi : decending order
template <class kotonoha>
using akane = priority_queue<kotonoha, akari<kotonoha>, greater<kotonoha>>;
template <class kotonoha>
using aoi = priority_queue<kotonoha>;

//------------------------------- Dubug Functions ---------------------------//
inline void print()
{
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest)
{
    cout << first << ' ';
    print(rest...);
}
//------------------------------- Solver ------------------------------------//

void solve()
{
    int n, m, q;
    cin >> n >> m >> q;
    yukari<int> g(n);
    UnionFind uf(n);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
        uf.merge(u, v);
    }

    LowestCommonAncestor lca(n, g);
    akari<i64> ws(n);
    i64 ans = 0;
    for (int i = 0; i < q; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (uf.same(a, b))
        {
            ans += (i64)lca.dist(a, b);
        }
        else
        {
            ws[a]++;
            ws[b]++;
        }
    }
    akari<map<int, pair<i64, i64>>> dp(n);
    auto calc = [&](auto &&calc, int v, int p, bool flag) -> pair<i64, i64> {
        if (dp[v].count(p))
        {
            return dp[v][p];
        }
        //res = {val, dif}
        pair<i64, i64> res = make_pair(0, ws[v]);
        if (flag || p == -1)
        {
            for (auto nv : g[v])
            {
                if (nv == p)
                {
                    continue;
                }
                auto chi = calc(calc, nv, v, flag);
                res.first += chi.first + chi.second;
                res.second += chi.second;
            }
        }
        else
        {
            auto par = calc(calc, p, v, 0);
            auto ard = calc(calc, v, -1, 0);
            res.first = ard.first - par.first - par.second;
            res.second = ard.second - par.second;
        }
        return dp[v][p] = res;
    };
    //uf の代表に対して呼ぶ
    for (int v = 0; v < n; v++)
    {
        if (v == uf.root(v))
        {
            calc(calc, v, -1, 1);
        }
    }
    akari<i64> sum(n, 1LL << 60);
    for (int v = 0; v < n; v++)
    {
        sum[uf.root(v)] = min(sum[uf.root(v)], calc(calc, v, -1, 0).first);
        //print(v, calc(calc, v, -1, 0).first, calc(calc, v, -1, 0).second);
    }
    for (int v = 0; v < n; v++)
    {
        if (v == uf.root(v))
        {
            ans += sum[v];
        }
    }
    cout << ans << endl;
}

int main()
{
    solve();
    return 0;
}
0