Submission #3448350


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, i_i> i_i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
struct UnionFind {
    vector<int> par;
    vector<int> rank;

    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n + 1); rank.resize(n + 1);
        for (int i = 0; i <= n; ++i) par[i] = i, rank[i] = 0;
    }

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

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

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


int main() {
    //cout.precision(10);
    UnionFind uni(200500);
    int n, m, k;
    vector<i_i_i> edges;
    cin >> n >> m >> k;
    if(k == 1){
        cout << 0 << endl;
        return 0;
    }
    int c[100200];
    for(int i = 1; i <= n; i++){
        cin >> c[i];
    }
    for(int i = 1; i <= m; i++){
        int a, b;
        ll w;
        cin >> a >> b >> w;
        edges.push_back({w, {a, b}});
    }
    ll ans = 0;
    sort(edges.begin(), edges.end());
    int components = k;
    for(int i = 0; i < edges.size(); i++){
        i_i_i now = edges[i];
        int ca = c[now.second.first];
        int cb = c[now.second.second];
        int cost = now.first;
        if(ca == 0){
            ca = now.second.first + 100000;
        }
        if(cb == 0){
            cb = now.second.second + 100000;
        }
        if(uni.issame(ca, cb)) continue;
        uni.merge(ca, cb);
        components--;
        ans += cost;
        if(components == 1){
            cout << ans << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Submission Info

Submission Time
Task A - Colorful MST
User kort0n
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2129 Byte
Status AC
Exec Time 127 ms
Memory 4340 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 0 / 0 100 / 100 100 / 100 200 / 200 300 / 300
Status
AC × 4
AC × 7
AC × 12
AC × 7
AC × 28
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt
Subtask1 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt
Subtask2 s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s2_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt
Subtask3 00_example_02.txt, s3_13.txt, s3_14.txt, s3_15.txt, s3_16.txt, s3_17.txt, s3_18.txt
Subtask4 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 00_example_04.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s2_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s3_13.txt, s3_14.txt, s3_15.txt, s3_16.txt, s3_17.txt, s3_18.txt, s4_19.txt, s4_20.txt, s4_21.txt, s4_22.txt, s4_23.txt, s4_24.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 2 ms 1792 KB
00_example_02.txt AC 2 ms 1792 KB
00_example_03.txt AC 2 ms 1792 KB
00_example_04.txt AC 2 ms 1792 KB
s1_01.txt AC 2 ms 1792 KB
s1_02.txt AC 124 ms 4340 KB
s1_03.txt AC 2 ms 1792 KB
s1_04.txt AC 2 ms 1792 KB
s1_05.txt AC 67 ms 3320 KB
s1_06.txt AC 125 ms 4340 KB
s2_07.txt AC 18 ms 2304 KB
s2_08.txt AC 127 ms 4340 KB
s2_09.txt AC 94 ms 4212 KB
s2_10.txt AC 88 ms 4212 KB
s2_11.txt AC 119 ms 4340 KB
s2_12.txt AC 118 ms 4340 KB
s3_13.txt AC 16 ms 2304 KB
s3_14.txt AC 119 ms 4340 KB
s3_15.txt AC 91 ms 4212 KB
s3_16.txt AC 85 ms 4212 KB
s3_17.txt AC 112 ms 4340 KB
s3_18.txt AC 109 ms 4340 KB
s4_19.txt AC 17 ms 2304 KB
s4_20.txt AC 117 ms 4340 KB
s4_21.txt AC 93 ms 4212 KB
s4_22.txt AC 90 ms 4212 KB
s4_23.txt AC 120 ms 4340 KB
s4_24.txt AC 118 ms 4340 KB