結果

問題 No.922 東北きりきざむたん
ユーザー mamekinmamekin
提出日時 2019-11-09 13:57:24
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 293 ms / 2,000 ms
コード長 6,492 bytes
コンパイル時間 1,612 ms
コンパイル使用メモリ 138,268 KB
実行使用メモリ 32,016 KB
最終ジャッジ日時 2023-10-13 07:06:19
合計ジャッジ時間 6,411 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,352 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 1 ms
4,352 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 1 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 62 ms
12,160 KB
testcase_10 AC 53 ms
5,740 KB
testcase_11 AC 62 ms
10,020 KB
testcase_12 AC 26 ms
12,752 KB
testcase_13 AC 19 ms
5,432 KB
testcase_14 AC 104 ms
17,104 KB
testcase_15 AC 17 ms
13,472 KB
testcase_16 AC 199 ms
18,792 KB
testcase_17 AC 211 ms
18,856 KB
testcase_18 AC 200 ms
19,056 KB
testcase_19 AC 206 ms
18,784 KB
testcase_20 AC 205 ms
18,728 KB
testcase_21 AC 293 ms
22,048 KB
testcase_22 AC 293 ms
21,780 KB
testcase_23 AC 238 ms
20,472 KB
testcase_24 AC 229 ms
20,412 KB
testcase_25 AC 192 ms
19,224 KB
testcase_26 AC 191 ms
19,204 KB
testcase_27 AC 197 ms
19,104 KB
testcase_28 AC 87 ms
15,508 KB
testcase_29 AC 246 ms
32,016 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

class UnionFindTree
{
private:
    int n;
    int groupNum;       // グループの数
    vector<int> parent; // 親ノード
    vector<int> rank;   // 木の高さの上限
    vector<int> num;    // グループの要素数
    int find(int i){
        if(parent[i] == i)
            return i;
        else
            return parent[i] = find(parent[i]);
    }
public:
    UnionFindTree(int n){ // コンストラクタ
        this->n = n;
        groupNum = n;
        parent.resize(n);
        for(int i=0; i<n; ++i)
            parent[i] = i;
        rank.assign(n, 0);
        num.assign(n, 1);
    }
    void unite(int a, int b){ // aとbのグループを併合
        if((a = find(a)) != (b = find(b))){
            if(rank[a] < rank[b]){
                parent[a] = b;
                num[b] += num[a];
            }
            else{
                parent[b] = a;
                if(rank[a] == rank[b])
                    ++ rank[a];
                num[a] += num[b];
            }
            -- groupNum;
        }
    }
    bool same(int a, int b){ // aとbのグループが同じかを調べる
        return find(a) == find(b);
    }
    int getNum(){ // グループの数を返す
        return groupNum;
    }
    int getNum(int a){ // aのグループの要素数を返す
        return num[find(a)];
    }
};

template <class T>
class EdgeBase
{
public:
    int to;
    T cost;
    EdgeBase(){};
    EdgeBase(int to0, T cost0){to = to0; cost = cost0;}
};
typedef EdgeBase<int> Edge;

template<class T>
class LowestCommonAncestor
{
private:
    vector<vector<int> > to; // ダブリング先のノード
    vector<int> depth;       // 根からの深さ
    vector<T> dist;          // 根からの距離
    int climb(int curr, int len)
    {
        int i = 0;
        while(len > 0){
            if(len % 2 == 1)
                curr = to[curr][i];
            len /= 2;
            ++ i;
        }
        return curr;
    }
public:
    LowestCommonAncestor(const vector<vector<EdgeBase<T> > >& edges, int root)
    {
        int n = edges.size();
        to.assign(n, vector<int>());
        dist.assign(n, 0);
        depth.assign(n, 0);

        queue<pair<int, int> > q;
        q.push(make_pair(root, -1));

        int cnt = 0;
        while(!q.empty()){
            int m = q.size();
            while(--m >= 0){
                int curr, prev;
                tie(curr, prev) = q.front();
                q.pop();

                if(prev != -1){
                    to[curr].push_back(prev);
                    int j = prev;
                    for(unsigned k=0; k<to[j].size(); ++k){
                        j = to[j][k];
                        to[curr].push_back(j);
                    }
                }

                for(const EdgeBase<T>& e : edges[curr]){
                    if(e.to != prev){
                        depth[e.to] = depth[curr] + 1;
                        dist[e.to] = dist[curr] + e.cost;
                        q.push(make_pair(e.to, curr));
                    }
                }
            }
            ++ cnt;
        }
    }
    // 2つのノードの最小共通祖先を取得
    int getAncestor(int a, int b)
    {
        int diff = depth[a] - depth[b];
        if(diff < 0)
            b = climb(b, -diff);
        else
            a = climb(a, diff);
        if(a == b)
            return a;

        for(int i=to[a].size()-1; i>=0; --i){
            if(i < (int)to[a].size() && to[a][i] != to[b][i]){
                a = to[a][i];
                b = to[b][i];
            }
        }
        return to[a][0];
    }
    // ノードの深さを取得
    int getDepth(int a)
    {
        return depth[a];
    }
    // 2つのノードの距離を取得
    T getDist(int a, int b)
    {
        int c = getAncestor(a, b);
        return dist[a] + dist[b] - dist[c] * 2;
    }
};

const int INF = INT_MAX / 4;

void dfs1(const vector<vector<Edge> >& edges, const vector<int>& cnt, int curr, int prev, vector<pair<int, long long> >& v)
{
    v[curr] = make_pair(cnt[curr], 0);
    for(const auto& e : edges[curr]){
        int next = e.to;
        if(next == prev)
            continue;
        dfs1(edges, cnt, next, curr, v);
        v[curr].first += v[next].first;
        v[curr].second += v[next].second + v[next].first;
    }
}

long long dfs2(const vector<vector<Edge> >& edges, int curr, int prev, const vector<pair<int, long long> >& v, pair<int, long long> p)
{
    pair<int, long long> sum = v[curr];
    sum.first += p.first;
    sum.second += p.second + p.first;

    long long ans = sum.second;
    for(const auto& e : edges[curr]){
        int next = e.to;
        if(next == prev)
            continue;
        pair<int, long long> p2 = sum;
        p2.first -= v[next].first;
        p2.second -= v[next].second + v[next].first;
        ans = min(ans, dfs2(edges, next, curr, v, p2));
    }
    return ans;
}

int main()
{
    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<Edge> > edges(n+1);
    UnionFindTree uft(n+1);
    for(int i=0; i<m; ++i){
        int u, v;
        cin >> u >> v;
        edges[u].push_back(Edge(v, 1));
        edges[v].push_back(Edge(u, 1));
        uft.unite(u, v);
    }
    for(int i=1; i<=n; ++i){
        if(!uft.same(0, i)){
            edges[0].push_back(Edge(i, INF));
            uft.unite(0, i);
        }
    }
    LowestCommonAncestor<int> lca(edges, 0);

    vector<int> cnt(n+1, 0);
    long long ans = 0;
    for(int i=0; i<q; ++i){
        int a, b;
        cin >> a >> b;
        int dist = lca.getDist(a, b);
        if(dist < INF){
            ans += dist;
        }
        else{
            ++ cnt[a];
            ++ cnt[b];
        }
    }

    vector<pair<int, long long> > v(n+1, make_pair(-1, -1));
    for(int i=1; i<=n; ++i){
        if(v[i].first != -1)
            continue;
        dfs1(edges, cnt, i, -1, v);
        ans += dfs2(edges, i, -1, v, make_pair(0, 0));
    }
    cout << ans << endl;

    return 0;
}
0