Submission #1245972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245972		khoi	Sirni (COCI17_sirni)	C++20	0 / 140	5096 ms	832 KiB

sirni

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

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

struct DSU {
    vector<int> p, r;
    DSU(int n): p(n), r(n,0) { iota(p.begin(), p.end(), 0); }
    int find_set(int x){ return p[x]==x?x:p[x]=find_set(p[x]); }
    bool union_set(int a,int b){
        a=find_set(a); b=find_set(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;
    }
};

const int MAXV = 10000000;
static int nxt[MAXV+5];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    vector<int> P(n);
    for(int i=0;i<n;i++) cin>>P[i];
    sort(P.begin(), P.end());
    P.erase(unique(P.begin(), P.end()), P.end());
    n = P.size();

    // build nxt[x] = index in P of the smallest P[idx]>=x
    for(int i=0;i<n-1;i++){
        for(int x=P[i]; x<P[i+1]; x++){
            nxt[x] = i+1;
            // skip ahead
            x = P[nxt[x]]/P[i]*P[i] - 1;
        }
        nxt[P[i]] = i;
    }
    nxt[P[n-1]] = n-1;
    int mx = P[n-1];

    // --- Chuẩn bị DSU trước, rồi trong vòng sinh cạnh xử lý luôn các w==0 ---
    DSU dsu(n);
    vector<Edge> e;
    e.reserve(n * 20);  // ước lượng trung bình

    for(int i=0;i<n;i++){
        // cạnh “kề sau” p[i]→p[i]+1
        int jidx = nxt[min(mx, P[i]+1)];
        int w = P[jidx] % P[i];
        if(w==0){
            dsu.union_set(i, jidx);
        } else {
            e.push_back({i, jidx, w});
        }

        // duyệt các bậc blocks theo p[i]
        for(int x = P[i] + P[i]; x <= mx; x += P[i]){
            int idx = nxt[x];
            w = P[idx] % P[i];
            if(w==0){
                dsu.union_set(i, idx);
            } else {
                e.push_back({i, idx, w});
            }
            // nhảy x lên block tiếp theo
            x = (P[idx] / P[i]) * P[i];
        }
    }

    // sort và Kruskal như cũ, nhưng DSU đã có một số liên kết w=0
    sort(e.begin(), e.end());
    long long total = 0;
    int need = n-1;
    // đếm xem DSU đã nối được bao nhiêu cạnh
    for(int i=0;i<n;i++){
        if(dsu.find_set(i) == i) need--; 
        // mỗi “root” nghĩa là 1 cây, tổng cần (cây–1)=n–1 nhưng ta đã union-zero trước
    }
    for(auto &E : e){
        if(need==0) break;
        if(dsu.union_set(E.u, E.v)){
            total += E.w;
            need--;
        }
    }

    cout<<total<<"\n";
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14