Submission #1061266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061266		thinknoexit	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	142 ms	16540 KiB

reconstruction

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge {
    int u, v, w;
    bool operator < (const Edge& o) const {
        return w < o.w;
    }
} e[100100], e2[100100];
int w[100100];
ll qs[100100];
int p[505];
int fr(int i) {
    return p[i] == i ? i : p[i] = fr(p[i]);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= m;i++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    int q;
    cin >> q;
    if (q <= 10) {
        while (q--) {
            int x;
            cin >> x;
            for (int i = 1;i <= m;i++) {
                e2[i].u = e[i].u;
                e2[i].v = e[i].v;
                e2[i].w = abs(e[i].w - x);
            }
            for (int i = 1;i <= n;i++) p[i] = i;
            sort(e2 + 1, e2 + 1 + m);
            ll ans = 0;
            for (int i = 1;i <= m;i++) {
                int pu = fr(e2[i].u), pv = fr(e2[i].v);
                if (pu == pv) continue;
                ans += e2[i].w;
                p[pu] = pv;
            }
            cout << ans << '\n';
        }
        return 0;
    }
    sort(e + 1, e + 1 + m);
    for (int i = 1;i <= m;i++) {
        w[i] = e[i].w;
        qs[i] = qs[i - 1] + w[i];
    }
    ll p = 0;
    while (q--) {
        int x;
        cin >> x;
        while (p < n && w[p + 1] <= x) p++;
        cout << (p * x - qs[p]) + ((qs[n] - qs[p]) - (n - p) * x) << '\n';
    }
    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23