Submission #1124576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124576		_8_8_	Security Guard (JOI23_guard)	C++20	100 / 100	723 ms	123228 KiB

guard

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int)2e5 + 12;
const ll inf = (ll)1e10;

int n, m, q, s[N], sz[N], p[N], f[N];
set<array<ll, 3>> g[N], g1[N];
int get(int v) {
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
bool merge1(int a, int b) {
    a = get(a);
    b = get(b);
    if(a == b) return 0;
    p[a] = b;
    return 1;
}

priority_queue<array<ll, 3>> st;

ll add;
vector<pair<int, int>> e;

void adde(int i) {
    if(!g1[i].empty()) {
        auto [val, x, y] = (*g1[i].begin());
        // cerr << i << ' ' << x << ' ' << y << "A\n";
        assert(get(x) != get(y));
        st.push({-(val - f[i]), x, y});
    }
}
void make() {
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        e.emplace_back(u, v);
    }
    sort(e.begin(), e.end(), [&](pair<int, int> x, pair<int, int> y){
        int X = (s[x.first] + s[x.second]);
        int Y = (s[y.first] + s[y.second]);
        return X < Y;
    });
    vector<pair<int, int>> e_;
    for(auto [x, y] : e) {
        if(merge1(x, y)) {
            e_.emplace_back(x, y);
            g1[x].insert({s[y] + s[x], x, y});
            g1[y].insert({s[x] + s[y], y, x});
        }
    }
    e.swap(e_);
    for(int i = 1; i <= n; i++) {
        f[i] = s[i], p[i] = i;
    }
    for(int i = 1; i <= n; i++) {
        adde(i);
    }
}
ll res[N];
void test() {
    cin >> n >> m >> q;
    for(int i = 1, mx = 0; i <= n; i++) {
        cin >> s[i];    
        mx = max(mx, s[i]);
        add -= s[i];
        p[i] = i;
        if(i == n) {
            add += mx;
        }
    }
    make();
    int mn = s[1];
    for(int i = 1; i <= n; i++) {
        res[n - 1] += s[i];
        mn = min(mn, s[i]);
    }
    res[n - 1] += mn * 1ll * (n - 2);
    int it = n - 2;
    while(it >= 0 && (!st.empty())) {
        array<ll, 3> j  = st.top();
        auto [val, x, y] = j;
        val *= -1;
        st.pop();
        if(get(x) == get(y) || val != s[x] + s[y] - max(f[get(x)], f[get(y)])) continue;
        int a = get(x), b = get(y);
        if((int)g1[a].size() < (int)g1[b].size()) {
            swap(x, y);
            swap(a, b);
            // g1[a].swap(g1[b]);
        }
        g1[a].erase({s[x] + s[y], x, y});
        for(auto [val, x, y] : g1[b]) {
            if(get(y) == a) continue;
            g1[a].insert({val, x, y});
        }
        res[it] = res[it + 1] - mn + val;
        p[b] = a;
        f[a] = min(f[a], f[b]);
        adde(a);
        it--;
    }
    
    for(int k = n; k <= q; k++) {
        res[k] = res[k - 1];
    }
    for(int i = 0; i <= q; i++) {
        cout << res[i] + add << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--)
        test();
}

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