oj.uz

Submission #729891

# Submission time Handle Problem Language Result Execution time Memory
729891 2023-04-24T18:52:17 Z kirakaminski968 Sirni (COCI17_sirni) C++17
112 / 140
 5000 ms 395500 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 556 KB Output is correct
2 Correct 57 ms 3496 KB Output is correct
3 Correct 3 ms 596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 440 ms 1244 KB Output is correct
3 Correct 3 ms 596 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 456 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 13788 KB Output is correct
2 Correct 608 ms 50588 KB Output is correct
3 Correct 251 ms 26016 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3608 KB Output is correct
2 Correct 337 ms 50556 KB Output is correct
3 Correct 170 ms 13788 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 50784 KB Output is correct
2 Correct 807 ms 100008 KB Output is correct
3 Correct 232 ms 26116 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6904 KB Output is correct
2 Correct 781 ms 99872 KB Output is correct
3 Correct 221 ms 26084 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 26216 KB Output is correct
2 Correct 4014 ms 395500 KB Output is correct
3 Correct 259 ms 26208 KB Output is correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 26184 KB Output is correct
2 Execution timed out 5076 ms 395420 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3784 KB Output is correct
2 Execution timed out 5032 ms 395440 KB Time limit exceeded
3 Halted 0 ms 0 KB -