Submission #1302750

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

construction

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

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

struct DSU {
    int n;
    vector<int> p, r;
    DSU(int n=0){ init(n); }
    void init(int n0){
        n = n0;
        p.resize(n);
        r.assign(n,0);
        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;
        if(r[a]<r[b]) swap(a,b);
        p[b]=a;
        if(r[a]==r[b]) r[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), Y(N);
    for(int i=0;i<N;i++) cin >> X[i] >> Y[i];
    struct Rect { ll P,Q,R,S; };
    vector<Rect> rects(M);
    for(int i=0;i<M;i++){
        cin >> rects[i].P >> rects[i].Q >> rects[i].R >> rects[i].S;
    }
    vector<pair<ll,int>> companies(C);
    for(int i=0;i<C;i++){
        ll B; int H;
        cin >> B >> H;
        companies[i] = {B, H};
    }

    // Tạo các cạnh: chỉ cho các cặp cùng x hoặc cùng y, kiểm tra xem đoạn thẳng có trùng hoặc chạm rect nào không.
    vector<Edge> edges;
    edges.reserve( (size_t)N * N / 4 );

    // Nhóm theo X để sinh các cặp cùng X
    unordered_map<ll, vector<int>> gx;
    gx.reserve(N*2);
    for(int i=0;i<N;i++) gx[X[i]].push_back(i);
    for(auto &kv : gx){
        auto &vec = kv.second;
        int k = (int)vec.size();
        // nếu muốn tối ưu, chỉ nối cặp k*(k-1)/2
        for(int i=0;i<k;i++){
            for(int j=i+1;j<k;j++){
                int a = vec[i], b = vec[j];
                ll x = X[a];
                ll y1 = Y[a], y2 = Y[b];
                ll lo = min(y1,y2), hi = max(y1,y2);
                bool ok = true;
                for(int t=0;t<M;t++){
                    ll P = rects[t].P, Q = rects[t].Q, R = rects[t].R, S = rects[t].S;
                    // đoạn đứng ở x; nếu x in [P,R] và y-interval giao với [Q,S] (kể cả chỉ chạm)
                    if(x >= P && x <= R){
                        ll inter_lo = max(lo, Q);
                        ll inter_hi = min(hi, S);
                        if(inter_lo <= inter_hi){
                            ok = false; break;
                        }
                    }
                }
                if(ok){
                    edges.push_back({a,b, llabs(y1-y2)});
                }
            }
        }
    }

    // Nhóm theo Y để sinh các cặp cùng Y
    unordered_map<ll, vector<int>> gy;
    gy.reserve(N*2);
    for(int i=0;i<N;i++) gy[Y[i]].push_back(i);
    for(auto &kv : gy){
        auto &vec = kv.second;
        int k = (int)vec.size();
        for(int i=0;i<k;i++){
            for(int j=i+1;j<k;j++){
                int a = vec[i], b = vec[j];
                ll y = Y[a];
                ll x1 = X[a], x2 = X[b];
                ll lo = min(x1,x2), hi = max(x1,x2);
                bool ok = true;
                for(int t=0;t<M;t++){
                    ll P = rects[t].P, Q = rects[t].Q, R = rects[t].R, S = rects[t].S;
                    // đoạn ngang ở y; nếu y in [Q,S] và x-interval giao với [P,R]
                    if(y >= Q && y <= S){
                        ll inter_lo = max(lo, P);
                        ll inter_hi = min(hi, R);
                        if(inter_lo <= inter_hi){
                            ok = false; break;
                        }
                    }
                }
                if(ok){
                    edges.push_back({a,b, llabs(x1-x2)});
                }
            }
        }
    }

    // Sắp cạnh theo trọng số tăng dần
    sort(edges.begin(), edges.end());

    // Tính comp_all = số thành phần khi dùng tất cả các cạnh hợp lệ
    DSU dsu_all(N);
    int comp_all = N;
    for(auto &e : edges){
        if(dsu_all.unite(e.u, e.v)) comp_all--;
    }

    // Với mỗi công ty xử lý Kruskal có điều kiện
    // (vì C <= 100 nên chạy lại Kruskal cho từng công ty là được)
    for(int idx=0; idx<C; idx++){
        ll B = companies[idx].first;
        int H = companies[idx].second;
        if(H < comp_all){
            cout << -1 << '\n';
            continue;
        }
        DSU dsu(N);
        int comps = N;
        long long sumEdges = 0;
        for(auto &e : edges){
            int u = e.u, v = e.v;
            ll w = e.w;
            if(dsu.find(u) == dsu.find(v)) continue;
            if(w < B || comps > H){
                // nối
                dsu.unite(u,v);
                sumEdges += w;
                comps--;
                if(comps == H && w >= B){
                    // we have reached required components; but still need to continue
                    // NOTE: if further edges with w < B exist they should still be added because they reduce cost.
                    // However since edges are sorted by w ascending, any later w will be >= current w.
                    // So to implement correctly we don't early break here; keep processing so that edges with w < B (smaller) are already processed earlier.
                }
            } else {
                // w >= B and comps <= H -> không cần nối, vì thêm cạnh này không giảm chi phí (w >= B)
                // và không bắt buộc (đã <= H)
                // do các cạnh sau có w tăng dần, không có gì cần làm
                // nhưng vẫn tiếp tục vì có thể có cạnh sau có w < B (không thể do sắp tăng dần)
            }
        }
        if(comps > H){
            // cố gắng nối nhưng không đủ cạnh để giảm xuống H
            cout << -1 << '\n';
        } else {
            long long total = sumEdges + (long long)comps * B;
            cout << total << '\n';
        }
    }

    return 0;
}

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