結果

問題 No.860 買い物
ユーザー mamekin
提出日時 2019-08-10 12:39:57
言語 C++14
(gcc 8.3.0)
結果
AC  
実行時間 147 ms
コード長 2,487 Byte
コンパイル時間 1,126 ms
使用メモリ 5,748 KB
最終ジャッジ日時 2019-10-25 14:35:39

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 4 ms
1,508 KB
sample2.txt AC 3 ms
1,508 KB
sample3.txt AC 3 ms
1,512 KB
test1.txt AC 2 ms
1,508 KB
test2.txt AC 3 ms
1,520 KB
test3.txt AC 3 ms
1,520 KB
test4.txt AC 7 ms
1,644 KB
test5.txt AC 132 ms
5,744 KB
test6.txt AC 131 ms
5,744 KB
test7.txt AC 134 ms
5,748 KB
test8.txt AC 131 ms
5,748 KB
test9.txt AC 91 ms
5,744 KB
test10.txt AC 90 ms
5,740 KB
test11.txt AC 130 ms
5,748 KB
test12.txt AC 132 ms
5,748 KB
test13.txt AC 62 ms
5,744 KB
test14.txt AC 104 ms
5,748 KB
test15.txt AC 147 ms
5,748 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)];
    }
};

int main()
{
    int n;
    cin >> n;
    vector<int> c(n), d(n);
    for(int i=0; i<n; ++i)
        cin >> c[i] >> d[i];

    vector<tuple<int, int, int> > v;
    for(int i=0; i<n; ++i)
        v.push_back(make_tuple(c[i], i, n));
    for(int i=1; i<n; ++i)
        v.push_back(make_tuple(d[i], i-1, i));
    sort(v.begin(), v.end());

    UnionFindTree uft(n+1);
    long long ans = accumulate(c.begin(), c.end(), 0LL);
    for(const auto& t: v){
        int cost, i, j;
        tie(cost, i, j) = t;
        if(!uft.same(i, j)){
            ans += cost;
            uft.unite(i, j);
        }
    }
    cout << ans << endl;

    return 0;
}
0