Submission #1139301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139301		ChottuF	Sirni (COCI17_sirni)	C++20	0 / 140	6 ms	3400 KiB

sirni

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

struct DSU {
    vector<int> p, sz;
    int components; // track how many disjoint sets remain
    DSU(int n) : p(n), sz(n,1), components(n) {
        for(int i=0;i<n;i++){
            p[i] = i;
        }
    }
    int find_set(int v){
        return (p[v] == v ? v : p[v] = find_set(p[v]));
    }
    bool unite(int a,int b){
        a=find_set(a); b=find_set(b);
        if(a==b) return false;
        if(sz[a]<sz[b]) swap(a,b);
        p[b]=a; sz[a]+=sz[b];
        components--;
        return true;
    }
};

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

    int N; 
    cin >> N;
    vector<long long> arr(N);
    for(int i=0; i<N; i++){
        cin >> arr[i];
    }

    // We only need to DSU on "card indices" [0..N-1].
    // But we also want a quick way to find "which index (or one of them) has value v".
    // pos[v] will hold all indices i s.t. arr[i] = v.
    // rep[v] = one representative index for value v, or -1 if none.
    static vector<int> pos[100001];
    for(int v=0; v<=100000; v++){
        pos[v].clear();
    }

    long long maxVal = 0;
    for(int i=0; i<N; i++){
        long long v = arr[i];
        pos[v].push_back(i);
        if(v > maxVal) maxVal = v;
    }

    // DSU structure
    DSU dsu(N);

    // 1) Unify duplicates at cost 0
    //    (If a value v appears k>1 times, unify those cards for free.)
    for(int v=1; v<=100000; v++){
        auto &indVec = pos[v];
        if(indVec.size() > 1){
            // unify them all with the first
            for(int j=1; j<(int)indVec.size(); j++){
                dsu.unite(indVec[0], indVec[j]);
            }
        }
    }

    // rep[v] = "some index whose card value == v", or -1 if none
    vector<int> rep(100001, -1);
    for(int v=1; v<=100000; v++){
        if(!pos[v].empty()){
            rep[v] = pos[v][0];
        }
    }

    // 2) For each v that appears, unify v with all multiples of v, at cost=0 if v divides those multiples exactly.
    //    We do a sieve-like pass: for m in {2v, 3v, 4v, ... up to maxVal}:
    //         if m also appears, unify rep[v], rep[m].
    //    This step merges big chunks of the graph for free.
    for(int v=1; v<=maxVal; v++){
        if(rep[v] == -1) continue;  // no card with value v
        for(long long m = 2LL*v; m <= maxVal; m += v){
            if(m <= 100000 && rep[m] != -1){
                // unify them at cost=0
                dsu.unite(rep[v], rep[m]);
            }
        }
    }

    // 3) Build edges for consecutive distinct values (in ascending order).
    //    Store them in a vector so we can Kruskal by cost.
    vector<long long> distinct;
    distinct.reserve(N); 
    for(int v=1; v<=maxVal; v++){
        if(rep[v] != -1) {
            distinct.push_back(v);
        }
    }

    sort(distinct.begin(), distinct.end()); // ascending
    vector<array<long long,3>> edges; // {cost, indexA, indexB}

    // consecutive distinct values => cost = (b % a) if a<b
    for(int i=0; i+1<(int)distinct.size(); i++){
        long long aVal = distinct[i];
        long long bVal = distinct[i+1];
        // cost:
        //   if aVal<bVal => cost = bVal % aVal ( < aVal )
        long long c = bVal % aVal;
        edges.push_back({c, rep[aVal], rep[bVal]});
    }

    // 4) Kruskal on those edges (sorted by cost).
    sort(edges.begin(), edges.end(),
         [](auto &A, auto &B){return A[0]<B[0];});

    long long ans = 0;
    for(auto &e : edges){
        long long c = e[0];
        int u = e[1], v = e[2];
        if(dsu.unite(u,v)){
            ans += c;
            // once DSU has 1 component, we can stop
            if(dsu.components==1) break;
        }
    }

    cout << ans << "\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