제출 #1151423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151423		ainta	Reconstruction Project (JOI22_reconstruction)	C++20	70 / 100	5092 ms	13408 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// Edge structure
struct Edge {
    int u, v;
    ll w;
};
 
// DSU structure for union-find.
struct DSU {
    vector<int> parent;
    DSU(int n) : parent(n) {
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }
    int find(int a) {
        return parent[a] == a ? a : parent[a] = find(parent[a]);
    }
    bool unite(int a, int b) {
        a = find(a), b = find(b);
        if(a == b) return false;
        parent[b] = a;
        return true;
    }
};
 
// Main function
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, M;
    cin >> N >> M;
    vector<Edge> edges(M);
    for (int i = 0; i < M; i++){
        int u, v; ll w;
        cin >> u >> v >> w;
        u--; v--; // convert to 0-index
        edges[i] = {u, v, w};
    }
    // Sort edges by weight in ascending order.
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b){
        return a.w < b.w;
    });
 
    // For each edge, we compute its range [L_i, R_i] such that it appears in the MST (with cost function |w-X|)
    // if and only if X is in that range.
    // We assume the allowed X range is [1, 10^9].
    const ll X_MIN = 1, X_MAX = 1000000000LL;
    vector<ll> Lbound(M), Rbound(M);
 
    for (int i = 0; i < M; i++){
        // --- Compute lower bound for edge i ---
        DSU dsu_lower(N);
        bool connected = false;
        ll L_val = X_MIN; // default: if no previous edge connects the endpoints, edge i is used for very small X.
        for (int j = i - 1; j >= 0; j--){
            dsu_lower.unite(edges[j].u, edges[j].v);
            if(dsu_lower.find(edges[i].u) == dsu_lower.find(edges[i].v)){
                // When the endpoints become connected,
                // we define lower bound as the average (rounded up) of the current edge’s weight and edge j’s weight.
                L_val = (edges[i].w + edges[j].w) / 2 + 1;
                connected = true;
                break;
            }
        }
        Lbound[i] = L_val;
 
        // --- Compute upper bound for edge i ---
        DSU dsu_upper(N);
        connected = false;
        ll R_val = X_MAX; // default: if no later edge connects them, then edge i is used for very high X.
        for (int j = i + 1; j < M; j++){
            dsu_upper.unite(edges[j].u, edges[j].v);
            if(dsu_upper.find(edges[i].u) == dsu_upper.find(edges[i].v)){
                // Define upper bound as the average (rounded down) of the current edge’s weight and edge j’s weight.
                R_val = (edges[i].w + edges[j].w) / 2;
                connected = true;
                break;
            }
        }
        Rbound[i] = R_val;
    }
 
    // For debugging, you might print out the ranges:
    // for (int i = 0; i < M; i++){
    //     cout << "Edge " << i+1 << " (w=" << edges[i].w << "): [" 
    //          << Lbound[i] << ", " << Rbound[i] << "]\n";
    // }
 
    // For each query X, the MST selected is exactly the set of edges i for which X is in [Lbound[i], Rbound[i]].
    // The total reconstruction cost is then:
    //   sum_{i: X in [Lbound[i], Rbound[i]]} |edges[i].w - X|
    int Q;
    cin >> Q;
    while(Q--){
        ll X;
        cin >> X;
        ll totalCost = 0;
        for (int i = 0; i < M; i++){
            if(Lbound[i] <= X && X <= Rbound[i]){
                if(X >= edges[i].w)
                    totalCost += (X - edges[i].w);
                else
                    totalCost += (edges[i].w - X);
            }
        }
        cout << totalCost << "\n";
    }
 
    return 0;
}

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