Submission #821624

#	Time	Username	Problem	Language	Result	Execution time	Memory
821624		rnl42	Reconstruction Project (JOI22_reconstruction)	C++14	7 / 100	5073 ms	7680 KiB

reconstruction

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

#ifdef DEBUG
#define dbg(x) cerr << #x << " = " << x << endl
#define dbgln() cerr << "\n"
#else
#define dbg(x) void(0)
#define dbgln() void(0)
#endif

struct Edge {
    int u, v, w;
    int val;
    bool operator<(const Edge& other) const {
        return val < other.val;
    }
};

struct UF {
    vector<int> uf;
    UF(int N) {
        uf.resize(N);
        iota(uf.begin(), uf.end(), 0);
    }
    int root(int u) {
        return u == uf[u] ? u : uf[u] = root(uf[u]);
    }
    void merge(int u, int v) {
        uf[root(u)] = root(v);
    }
};

int N, M, Q;
vector<Edge> edges;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> N >> M;
    edges.resize(M);
    for (int i = 0; i < M; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w, edges[i].u--, edges[i].v--;
    }
    cin >> Q;
    int x;
    for (int i = 0; i < Q; i++) {
        cin >> x;
        for (int j = 0; j < M; j++) {
            edges[j].val = abs(edges[j].w-x);
        }
        sort(edges.begin(), edges.end());
        UF uf(N);
        int ans = 0;
        for (auto& e : edges) {
            if (uf.root(e.u) != uf.root(e.v)) {
                ans += e.val;
                uf.merge(e.u, e.v);
            }
        }
        cout << ans << '\n';
    }
}

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