Submission #1245822

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

cities

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

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

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

bool unite(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return false;
    par[v] = u;
    has_important[u] |= has_important[v];
    return true;
}

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

    sort(edges.begin(), edges.end());
    for (int i = 1; i <= n; ++i) {
        par[i] = i;
        has_important[i] = false;
    }
    for (int x : imp) has_important[x] = true;

    long long res = 0;
    int groups = k;

    for (auto [w, u, v] : edges) {
        int ru = find(u), rv = find(v);
        if (ru == rv) continue;
        if (has_important[ru] || has_important[rv]) {
            unite(ru, rv);
            res += w;
            groups--;
            if (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