Submission #729891

#	Time	Username	Problem	Language	Result	Execution time	Memory
729891		kirakaminski968	Sirni (COCI17_sirni)	C++17	112 / 140	5076 ms	395500 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
struct edge{
    int weight,n1,n2;
};
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;
    }
};
bool cmp(edge x, edge y){
    return x.weight < y.weight;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<int> cards(n); vector<edge> edges;
    for(int i = 0;i<n;++i) cin >> cards[i];
    sort(cards.begin(),cards.end());
    cards.resize(unique(cards.begin(),cards.end()) - cards.begin());
    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;
            edge ne; ne.weight = cards[it]-j; ne.n1 = i; ne.n2 = it;
            edges.push_back(ne);
        }
    }
    DSU d; d.init(n); long long ans = 0;
    sort(edges.begin(),edges.end(),cmp);
    for(auto e : edges){
        if(d.unite(e.n1,e.n2)){
            //cout << e.n1 << " " << e.n2 << " " << e.weight << "\n";
            ans += e.weight;
        }
    }
    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: 0 / 14
• Subtask 10: 0 / 14