Submission #1188862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188862		zwezdinv	Security Guard (JOI23_guard)	C++20	50 / 100	147 ms	10488 KiB

guard

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

using ll = long long;

struct DSU {
    vector<int> p;

    DSU() = default;

    DSU(int n) : p(n) {
        iota(p.begin(), p.end(), 0);
    }

    int get(int u) {
        while (u != p[u]) u = p[u] = p[p[u]];
        return u;
    }

    bool unite(int u, int v) {
        u = get(u), v = get(v);
        if (u == v) return false;
        p[v] = u;
        return true;
    }
};

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, m, q;
    cin >> n >> m >> q;
    vector<ll> s(n);
    for (auto& i : s) cin >> i;
    vector<tuple<ll, int, int>> edges;
    ll base = *max_element(s.begin(), s.end()) - accumulate(s.begin(), s.end(), 0ll);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edges.emplace_back(s[u] + s[v], u, v);
    }
    sort(edges.begin(), edges.end());
    ll mst = 0;
    DSU dsu(n);
    for (auto [w, u, v] : edges) {
        mst += w * dsu.unite(u, v);
    }
    cout << mst + base;
}

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 13 / 13
• Subtask 5: 0 / 8
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24