結果

問題 No.922 東北きりきざむたん
ユーザー mamekin
提出日時 2019-11-09 13:57:24
言語 C++14
(gcc 8.3.0)
結果
AC  
実行時間 441 ms
コード長 6,492 Byte
コンパイル時間 1,246 ms
使用メモリ 30,340 KB
最終ジャッジ日時 2019-11-09 13:57:31

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0_sample_case1.txt AC 3 ms
6,872 KB
0_sample_case2.txt AC 2 ms
6,876 KB
0_sample_case3.txt AC 2 ms
6,876 KB
0_sample_case4.txt AC 4 ms
6,876 KB
1_small_case1.txt AC 3 ms
6,872 KB
1_small_case2.txt AC 2 ms
6,876 KB
1_small_case3.txt AC 4 ms
6,872 KB
1_small_case4.txt AC 3 ms
6,872 KB
1_small_case5.txt AC 4 ms
8,924 KB
2_random_case1.txt AC 88 ms
10,296 KB
2_random_case2.txt AC 70 ms
6,876 KB
2_random_case3.txt AC 85 ms
8,316 KB
2_random_case4.txt AC 31 ms
11,048 KB
2_random_case5.txt AC 26 ms
6,876 KB
2_random_case6.txt AC 139 ms
15,240 KB
2_random_case7.txt AC 19 ms
11,876 KB
3_0_hand_case1.txt AC 276 ms
17,136 KB
3_0_hand_case2.txt AC 302 ms
17,140 KB
3_0_hand_case3.txt AC 302 ms
17,136 KB
3_0_hand_case4.txt AC 290 ms
17,136 KB
3_0_hand_case5.txt AC 289 ms
17,136 KB
3_1_hand_case1.txt AC 441 ms
20,304 KB
3_1_hand_case2.txt AC 384 ms
20,304 KB
3_2_hand_case1.txt AC 304 ms
18,920 KB
3_2_hand_case2.txt AC 297 ms
18,988 KB
3_3_hand_case1.txt AC 305 ms
17,668 KB
3_3_hand_case2.txt AC 252 ms
17,668 KB
3_3_hand_case3.txt AC 245 ms
17,664 KB
4_corner_case1.txt AC 110 ms
13,796 KB
4_corner_case2.txt AC 313 ms
30,340 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