Submission #1139299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139299		ChottuF	Sirni (COCI17_sirni)	C++20	0 / 140	8 ms	4420 KiB

sirni

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

struct DSU {
    vector<int> p, sz;
    DSU(int n) {
        p.resize(n);
        sz.resize(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;
        if(sz[a] < sz[b]) swap(a,b);
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

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

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

    // DSU for connecting the N cards themselves
    DSU dsu(N);

    // pos[v] = indices of all cards whose value is v
    static vector<int> pos[100001];  // since Pi <= 1e5
    for(int v = 0; v <= 100000; v++){
        pos[v].clear();
    }
    for(int i = 0; i < N; i++){
        pos[arr[i]].push_back(i);
    }

    // First, unite all duplicate cards of the same value at cost 0
    for(int v = 1; v <= 100000; v++){
        if(pos[v].size() > 1){
            for(size_t i = 1; i < pos[v].size(); i++){
                dsu.unite(pos[v][0], pos[v][i]);
            }
        }
    }

    // rep[v] = an index (a “representative card”) that has value v,
    // or -1 if v does not appear
    vector<int> rep(100001, -1);
    for(int v = 1; v <= 100000; v++){
        if(!pos[v].empty()){
            rep[v] = pos[v][0];
        }
    }

    // Now, add zero‐cost edges where one value divides another.
    // For each v, if it appears, unite it with all multiples of v.
    // That gives cost = min(v mod m, m mod v) = 0 if v|m.
    for(int v = 1; v <= maxVal; v++){
        if(rep[v] == -1) continue; // value v not in array
        // We only sieve up to maxVal
        for(long long mult = 2LL*v; mult <= maxVal; mult += v){
            if(mult <= 100000 && rep[mult] != -1){
                dsu.unite(rep[v], rep[mult]);
            }
        }
    }

    // Next, gather all *distinct* values that actually appear
    // (in ascending order) so we can link “neighboring” values.
    vector<long long> distinct;
    distinct.reserve(N); 
    for(int v = 1; v <= maxVal; v++){
        if(rep[v] != -1){
            distinct.push_back(v);
        }
    }

    // Build candidate edges between consecutive distinct values.
    // cost = min(x % y, y % x).  If x < y then cost = y % x.
    // We'll just do y % x for consecutive ascending x < y.
    vector<array<long long,3>> edges; // {cost, rep_of_x, rep_of_y}

    for(int i = 0; i + 1 < (int)distinct.size(); i++){
        long long x = distinct[i];
        long long y = distinct[i+1];
        // since x < y, cost = y mod x
        long long c = y % x;
        edges.push_back({c, rep[x], rep[y]});
    }

    // Sort these edges by cost ascending
    sort(edges.begin(), edges.end(),
         [](auto &a, auto &b){return a[0] < b[0];});

    // Finally, Kruskal over those edges to connect any remaining
    // components.  We track how many DSU components remain in the
    // full set of N cards.
    // (In principle we could track it just among the distinct reps,
    // but it’s simpler to count the DSU parents of all N.)
    long long ans = 0;
    // Count how many DSU "leaders" are in the entire array
    int compCount = 0;
    for(int i = 0; i < N; i++){
        if(dsu.find(i) == i) compCount++;
    }

    // Kruskal: smallest edges first
    for(auto &e : edges){
        long long c = e[0];
        int a = e[1], b = e[2];
        if(dsu.unite(a,b)){
            ans += c;
            compCount--;
            if(compCount == 1) break; // all cards connected
        }
    }

    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