Submission #3449190


Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

const ll INF = 1LL << 50;
const int MAX_V = 100010;

class UnionFind {
public:
    // コンストラクタ
    explicit UnionFind(int N) : V_NUM(N) {
        for (int i = 0; i < V_NUM; ++i) {
            par[i] = i;
        }
        fill(rank, rank + V_NUM, 0);
    }

    // xの親を返す+更新
    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }

    // xとyを含むグループを統合する
    void unite(int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) return;

        if (rank[x] < rank[y]) swap(x, y);
        // rank[x] >= rank[y]

        // rankの大きい方、つまりxにyをくっつける
        par[y] = x;
        if (rank[x] == rank[y]) ++rank[x];
    }

    // xとyが同じグループに属するか判定
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    const int INF = 1 << 25;
    int V_NUM;
    int par[MAX_V], rank[MAX_V];
};

int main() {
    int N, M;
    cin >> N >> M;

    ll v[N + 1];
    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        cin >> v[i];
        ans += v[i];
    }

    UnionFind uf(N);
    int x[M], y[M];
    for (int i = 0; i < M; ++i) {
        cin >> x[i] >> y[i];

        // xとyを辺で結ぶ
        uf.unite(--x[i], --y[i]);
    }

    int sz[N];
    fill(sz, sz + N, 0);
    // sz[v] = vを親とするグラフが含む辺の本数

    for (int i = 0; i < M; ++i) {
        ++sz[uf.find(x[i])];
    }

    vector<int> child[N];
    // child[v] = vを親とするグラフが含む頂点の集合

    for (int i = 0; i < N; ++i) {
        child[uf.find(i)].push_back(i);
    }

    for (int i = 0; i < N; ++i) {
        // 条件:
        // 1. iがグラフの親である
        // 2. iを親とするグラフが木である
        if (i == uf.find(i) && child[i].size() == sz[i] + 1) {

            // このとき, 木から1つ頂点を選ぶことができなくなる
            ll del = INF;
            for (int j : child[i]) {
                del = min(del, v[j]);
            }

            ans -= del;
        }
    }

    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Treasure Hunt
User Tiramister
Language C++14 (GCC 5.4.1)
Score 200
Code Size 2399 Byte
Status AC
Exec Time 175 ms
Memory 7680 KB

Judge Result

Set Name All
Score / Max Score 200 / 200
Status
AC × 54
Set Name Test Cases
All 00_small_n_random0, 00_small_n_random1, 00_small_n_random2, 01_small_1g_random0, 01_small_1g_random1, 01_small_1g_random2, 02_small_mg_random0, 02_small_mg_random1, 02_small_mg_random2, 10_medium_n_random0, 10_medium_n_random1, 10_medium_n_random2, 11_medium_1g_random0, 11_medium_1g_random1, 11_medium_1g_random2, 12_medium_mg_random0, 12_medium_mg_random1, 12_medium_mg_random2, 20_large_n_random0, 20_large_n_random1, 20_large_n_random2, 21_large_1g_random0, 21_large_1g_random1, 21_large_1g_random2, 22_large_mg_random0, 22_large_mg_random1, 22_large_mg_random2, 23_large_n_max0, 23_large_n_max1, 23_large_n_max2, 23_large_n_max3, 23_large_n_max4, 24_large_1g_max0, 24_large_1g_max1, 24_large_1g_max2, 24_large_1g_max3, 24_large_1g_max4, 25_large_mg_max0, 25_large_mg_max1, 25_large_mg_max2, 25_large_mg_max3, 25_large_mg_max4, 26_corner0, 26_corner1, 26_corner2, 26_corner3, 26_corner4, 26_corner5, 26_corner6, sample01, sample02, sample03, sample04, sample05
Case Name Status Exec Time Memory
00_small_n_random0 AC 1 ms 256 KB
00_small_n_random1 AC 1 ms 256 KB
00_small_n_random2 AC 1 ms 256 KB
01_small_1g_random0 AC 1 ms 256 KB
01_small_1g_random1 AC 1 ms 256 KB
01_small_1g_random2 AC 1 ms 256 KB
02_small_mg_random0 AC 1 ms 256 KB
02_small_mg_random1 AC 1 ms 256 KB
02_small_mg_random2 AC 1 ms 256 KB
10_medium_n_random0 AC 1 ms 256 KB
10_medium_n_random1 AC 2 ms 256 KB
10_medium_n_random2 AC 2 ms 256 KB
11_medium_1g_random0 AC 2 ms 256 KB
11_medium_1g_random1 AC 2 ms 256 KB
11_medium_1g_random2 AC 2 ms 256 KB
12_medium_mg_random0 AC 2 ms 256 KB
12_medium_mg_random1 AC 2 ms 256 KB
12_medium_mg_random2 AC 2 ms 256 KB
20_large_n_random0 AC 97 ms 4864 KB
20_large_n_random1 AC 125 ms 3712 KB
20_large_n_random2 AC 80 ms 2304 KB
21_large_1g_random0 AC 66 ms 4988 KB
21_large_1g_random1 AC 21 ms 1408 KB
21_large_1g_random2 AC 61 ms 4092 KB
22_large_mg_random0 AC 50 ms 2432 KB
22_large_mg_random1 AC 76 ms 3712 KB
22_large_mg_random2 AC 89 ms 5632 KB
23_large_n_max0 AC 174 ms 6912 KB
23_large_n_max1 AC 174 ms 6912 KB
23_large_n_max2 AC 173 ms 6912 KB
23_large_n_max3 AC 173 ms 6912 KB
23_large_n_max4 AC 173 ms 6912 KB
24_large_1g_max0 AC 167 ms 6780 KB
24_large_1g_max1 AC 110 ms 6012 KB
24_large_1g_max2 AC 166 ms 6780 KB
24_large_1g_max3 AC 110 ms 6012 KB
24_large_1g_max4 AC 110 ms 6012 KB
25_large_mg_max0 AC 174 ms 7168 KB
25_large_mg_max1 AC 175 ms 7168 KB
25_large_mg_max2 AC 175 ms 7168 KB
25_large_mg_max3 AC 175 ms 7296 KB
25_large_mg_max4 AC 174 ms 7168 KB
26_corner0 AC 56 ms 7680 KB
26_corner1 AC 1 ms 256 KB
26_corner2 AC 104 ms 6012 KB
26_corner3 AC 43 ms 1024 KB
26_corner4 AC 137 ms 4352 KB
26_corner5 AC 131 ms 4352 KB
26_corner6 AC 131 ms 4352 KB
sample01 AC 1 ms 256 KB
sample02 AC 1 ms 256 KB
sample03 AC 1 ms 256 KB
sample04 AC 1 ms 256 KB
sample05 AC 1 ms 256 KB