Submission #1245820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245820		sheyer	Cities (BOI16_cities)	C++20	0 / 100	50 ms	3620 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];

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

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> m;
    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());

    vector<int> root(n + 1);
    for (int i = 1; i <= n; ++i) par[i] = i;

    long long res = 0;
    int cnt = 0;
    for (auto [w, u, v] : edges) {
        if (merge(u, v)) {
            res += w;
            ++cnt;
            if (cnt == n - 1) break;
        }
    }

    // tìm tập các nút gốc chứa điểm quan trọng
    set<int> imp_roots;
    for (int i = 0; i < k; ++i) imp_roots.insert(find(imp[i]));

    // nếu tất cả điểm quan trọng chung 1 component
    if (imp_roots.size() == 1) cout << res << '\n';
    else {
        // cần tìm MST chỉ để các điểm quan trọng liên thông
        vector<int> mark(n + 1, 0);
        for (int i = 1; i <= n; ++i) par[i] = i;
        for (int i = 0; i < k; ++i) mark[imp[i]] = 1;

        sort(edges.begin(), edges.end());
        res = 0;
        int components = k;

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

            if (mark[pu] && mark[pv]) {
                merge(pu, pv);
                mark[find(pu)] = 1;
                res += w;
                --components;
            }
            else if (mark[pu]) {
                merge(pu, pv);
                mark[find(pu)] = 1;
                res += w;
                --components;
            }
            else if (mark[pv]) {
                merge(pu, pv);
                mark[find(pu)] = 1;
                res += w;
                --components;
            }

            if (components == 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