제출 #1188886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188886		zwezdinv	Security Guard (JOI23_guard)	C++20	26 / 100	4091 ms	16684 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;
    }
};

int 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;
    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());
    vector<tuple<ll, int, int>> tr;
    vector<vector<int>> g(n);
    {
        DSU dsu(n);
        for (auto [w, u, v] : edges) {
            if (dsu.unite(u, v)) {
                tr.emplace_back(w, u, v);
            }
        }
    }
    vector<ll> ans(n);
    DSU dsu(n);
    vector<ll> mn = s;
    ll base = *max_element(s.begin(), s.end()) - accumulate(s.begin(), s.end(), 0ll);
    ll mst = accumulate(s.begin(), s.end(), 0ll);
    ll mns = *min_element(s.begin(), s.end());
    ans[n - 1] = mst + base + (n - 2) * mns;
    for (int k = n - 2; k >= 0; --k) {
        tuple<ll, int, int> opt = {-1, -1, -1};
        ll mnv = 1e18;
        for (auto [w, u, v] : tr) {
            u = dsu.get(u), v = dsu.get(v);
            if (u == v) continue;
            ll val = -max(mn[u], mn[v]) + w;
            if (val < mnv) {
                mnv = val;
                opt = {w, u, v};
            }
        }
        mst += mnv;
        auto [w, u, v] = opt;
        u = dsu.get(u), v = dsu.get(v);
        dsu.unite(u, v);
        mn[dsu.get(u)] = min(mn[u], mn[v]);
        ans[k] = mst + base + (k - 1) * mns;
    }
    for (int i = 0; i <= q; ++i) {
        cout << ans[min(n - 1, i)] << '\n';
    }
}

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