Submission #1194230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194230		SnowRaven52	Sirni (COCI17_sirni)	C++20	0 / 140	226 ms	286912 KiB

sirni

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

struct DisjointSets {
    vector<int> e;
    DisjointSets(int n): e(n, -1) { }
    int find(int x) {
        return e[x] < 0 ? x : e[x] = find(e[x]);
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (-e[a] > -e[b]) swap(a,b);
        e[b] += e[a];
        e[a] = b;
        return true;
    }
    bool connected(int a, int b) {
        return find(a) == find(b);
    }
};

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

    int n;
    cin >> n;
    vector<int> a(n);
    for(int &x : a) cin >> x;

    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    n = (int)a.size();

    int M = a.back();

    vector<int> nxt(M+2, 0);
    vector<vector<pair<int,int>>> edges(M+1);


    for(int i = 0; i < n; i++){
        nxt[a[i]] = -(i+1);
    }
    for(int i = M-1; i >= 0; i--){
        if(nxt[i] == 0){
            nxt[i] = nxt[i+1];
        }

        if (nxt[i] < 0) nxt[i] = -nxt[i];
    }

    for(int i = 0; i < n-1; i++){
        int ai = a[i];
        for(int j = ai; j <= M; j += ai){
            int idx = nxt[j]; 
            if (idx == 0) break;
            int at = a[idx - 1];
            int diff = at - j;
            if (diff < 0 || at >= ai + j) 
                continue;
            edges[diff].emplace_back(i+1, idx);
        }
    }

    DisjointSets dsu(n);
    long long ans = 0;
    for(int cost = 0; cost <= M; cost++){
        for(auto &e : edges[cost]){
            int u = e.first - 1;
            int v = e.second - 1;
            if (!dsu.connected(u, v)){
                dsu.unite(u, v);
                ans += cost;
            }
        }
    }
    cout << ans << endl;
}

• 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