Submission #1245823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245823		sheyer	Cities (BOI16_cities)	C++20	0 / 100	45 ms	3516 KiB

cities

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, k, m;
int imp[5];
vector<tuple<int, int, int>> edges;
int par[N];
bool has_imp[N];

int find(int u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

void unite(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    par[v] = u;
    has_imp[u] |= has_imp[v];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> m;
    for (int i = 0; i < k; ++i) {
        cin >> imp[i];
        has_imp[imp[i]] = true;
    }
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.emplace_back(w, u, v);
    }

    iota(par, par + N, 0);
    sort(edges.begin(), edges.end());

    long long res = 0;
    int important_groups = k;

    for (auto [w, u, v] : edges) {
        int ru = find(u), rv = find(v);
        if (ru == rv) continue;

        bool imp_u = has_imp[ru];
        bool imp_v = has_imp[rv];

        unite(ru, rv);
        if (imp_u && imp_v) important_groups--;
        else if (imp_u || imp_v) important_groups--;

        res += w;
        if (important_groups == 1) break;
    }

    cout << res << '\n';
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26