Submission #1302758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302758		vukhacminh	도로 건설 사업 (JOI13_construction)	C++20	0 / 100	5091 ms	4476 KiB

construction

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct DSU {
    int n;
    vector<int> p;
    DSU(int n=0): n(n), p(n+1) { for(int i=0;i<=n;i++) p[i]=i; }
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    bool unite(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return false;
        p[b]=a; return true;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, C;
    if(!(cin>>N>>M>>C)) return 0;
    vector<ll> X(N+1), Y(N+1);
    for(int i=1;i<=N;i++) cin>>X[i]>>Y[i];
    struct Rect { ll p,q,r,s; };
    vector<Rect> rects(M);
    for(int j=0;j<M;j++){
        cin>>rects[j].p>>rects[j].q>>rects[j].r>>rects[j].s;
    }
    vector<pair<ll,int>> companies(C);
    for(int k=0;k<C;k++){
        ll B; int H;
        cin>>B>>H;
        companies[k] = {B, H};
    }

    // Build edges: for any pair i<j with same X or same Y and not blocked by any rectangle.
    struct Edge { ll w; int u,v; };
    vector<Edge> edges;
    edges.reserve(min((long long)N*(N-1)/2, (long long)1000000)); // heuristic

    for(int i=1;i<=N;i++){
        for(int j=i+1;j<=N;j++){
            if(X[i]==X[j]){
                // vertical segment x = X[i], y in [minY,maxY]
                ll x0 = X[i];
                ll y1 = min(Y[i], Y[j]);
                ll y2 = max(Y[i], Y[j]);
                bool blocked = false;
                for(int t=0;t<M;t++){
                    // rectangle [p,r] x [q,s]; if x0 in [p,r] and y-interval intersects [q,s] -> blocked
                    if(x0 >= rects[t].p && x0 <= rects[t].r){
                        ll low = max(y1, rects[t].q);
                        ll high = min(y2, rects[t].s);
                        if(low <= high){ blocked = true; break; }
                    }
                }
                if(!blocked){
                    ll w = y2 - y1;
                    edges.push_back({w, i, j});
                }
            } else if(Y[i]==Y[j]){
                // horizontal segment y = Y[i], x in [minX,maxX]
                ll y0 = Y[i];
                ll x1 = min(X[i], X[j]);
                ll x2 = max(X[i], X[j]);
                bool blocked = false;
                for(int t=0;t<M;t++){
                    if(y0 >= rects[t].q && y0 <= rects[t].s){
                        ll low = max(x1, rects[t].p);
                        ll high = min(x2, rects[t].r);
                        if(low <= high){ blocked = true; break; }
                    }
                }
                if(!blocked){
                    ll w = x2 - x1;
                    edges.push_back({w, i, j});
                }
            }
        }
    }

    // Sort edges by weight for Kruskal
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b){ 
        if(a.w!=b.w) return a.w < b.w;
        if(a.u!=b.u) return a.u < b.u;
        return a.v < b.v;
    });

    // Kruskal to get MST edges (one MST per connected component)
    DSU dsu(N);
    vector<ll> mst_edges; mst_edges.reserve(N);
    ll total_mst_weight = 0;
    for(const auto &e: edges){
        if(dsu.unite(e.u, e.v)){
            total_mst_weight += e.w;
            mst_edges.push_back(e.w);
        }
    }

    // Count number of components K
    set<int> roots;
    for(int i=1;i<=N;i++) roots.insert(dsu.find(i));
    int K = (int)roots.size();

    // Sort MST edge weights descending to be able to "remove" largest edges when increasing airport count
    sort(mst_edges.begin(), mst_edges.end(), greater<ll>());
    int mstedges_count = (int)mst_edges.size(); // should equal N-K
    // prefix sums for quick sum of largest t edges
    vector<ll> pref(mstedges_count+1, 0);
    for(int i=1;i<=mstedges_count;i++) pref[i] = pref[i-1] + mst_edges[i-1];

    // For each company compute minimal cost
    for(int k=0;k<C;k++){
        ll B = companies[k].first;
        int H = (int)companies[k].second;
        if(H < K){
            cout << -1 << '\n';
            continue;
        }
        // s: number of airports (K .. min(H, N))
        ll best = LLONG_MAX;
        int smax = min(H, N);
        for(int s = K; s <= smax; s++){
            int remove = s - K; // number of largest MST edges we can remove
            // remove <= mstedges_count (since mstedges_count = N-K and s<=N)
            ll removed_sum = (remove<=mstedges_count) ? pref[remove] : pref[mstedges_count];
            ll road_cost = total_mst_weight - removed_sum;
            ll total_cost = road_cost + B * (ll)s;
            if(total_cost < best) best = total_cost;
        }
        cout << best << '\n';
    }

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30