Submission #729900

#	Time	Username	Problem	Language	Result	Execution time	Memory
729900		kirakaminski968	Sirni (COCI17_sirni)	C++17	140 / 140	3209 ms	686780 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7+100;
vector<array<int,3>> edges[N];
struct DSU {
    vector<int> e; void init(int N) { e = vector<int>(N,-1); }
    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
    bool sameSet(int a, int b) { return get(a) == get(b); }
    int size(int x) { return -e[get(x)]; }
    bool unite(int x, int y) {
      x = get(x), y = get(y); if (x == y) return 0;
      if (e[x] > e[y]) swap(x,y);
      e[x] += e[y]; e[y] = x; return 1;
    }
};
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n; vector<int> cards(n);
    for(int i = 0;i<n;++i) cin >> cards[i];
    sort(cards.begin(),cards.end());
    cards.resize(unique(cards.begin(),cards.end()) - cards.begin());
    DSU d; d.init(n);
    n = cards.size();
    for(int i = 0;i<n-1;++i){
        for(int j = cards[i];j<=cards.back();j+=cards[i]){
            int it = lower_bound(cards.begin()+i+1,cards.end(),j)-cards.begin();
            if(it >= n || cards[it]-j > cards[i]) continue;
            edges[cards[it]-j].push_back({cards[it]-j,it,i});
        }
    }
    long long ans = 0;
    for(int i = 0;i<N;++i){
        for(auto u : edges[i]){
            if(d.unite(u[1],u[2])){
                ans += u[0];
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

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