Submission #1194231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194231		SnowRaven52	Sirni (COCI17_sirni)	C++20	0 / 140	208 ms	292064 KiB

sirni

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

struct DSU {
    vector<int> p;
    DSU(int n): p(n, -1) {}
    int find(int x){
        return p[x]<0 ? x : p[x] = find(p[x]);
    }
    bool unite(int x, int y){
        x = find(x); y = find(y);
        if(x==y) return false;
        if(-p[x] > -p[y]) swap(x,y);
        p[y] += p[x];
        p[x] = y;
        return true;
    }
};

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

    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

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

    int M = a.back();

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

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

    for(int i = 0; i < n; i++){
        int ai = a[i];
        for(int j = ai; j <= M; j += ai){
            int idx1 = nxt[j];
            if(idx1 == 0) 
                break;
            int k = idx1 - 1;
            if(k <= i) 
                continue;
            int cost = a[k] - j;
            edges[cost].push_back({i, k});
        }
    }

    DSU dsu(n);
    long long ans = 0;
    for(int c = 0; c <= M; c++){
        for(auto &e : edges[c]){
            if(dsu.unite(e.first, e.second)){
                ans += c;
            }
        }
    }

    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