oj.uz

Submission #729900

# Submission time Handle Problem Language Result Execution time Memory
729900 2023-04-24T19:13:31 Z kirakaminski968 Sirni (COCI17_sirni) C++17
140 / 140
 3209 ms 686780 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 235300 KB Output is correct
2 Correct 160 ms 238868 KB Output is correct
3 Correct 144 ms 235372 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 235324 KB Output is correct
2 Correct 569 ms 236384 KB Output is correct
3 Correct 128 ms 235440 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 235296 KB Output is correct
2 Correct 140 ms 235180 KB Output is correct
3 Correct 126 ms 235352 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 250000 KB Output is correct
2 Correct 521 ms 290152 KB Output is correct
3 Correct 287 ms 259152 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 237628 KB Output is correct
2 Correct 309 ms 267928 KB Output is correct
3 Correct 235 ms 250012 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 269188 KB Output is correct
2 Correct 635 ms 313296 KB Output is correct
3 Correct 272 ms 256464 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 240172 KB Output is correct
2 Correct 582 ms 306872 KB Output is correct
3 Correct 273 ms 256688 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 253760 KB Output is correct
2 Correct 2332 ms 546548 KB Output is correct
3 Correct 291 ms 257132 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 253380 KB Output is correct
2 Correct 3209 ms 686780 KB Output is correct
3 Correct 409 ms 263996 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 238684 KB Output is correct
2 Correct 2950 ms 677296 KB Output is correct
3 Correct 294 ms 259216 KB Output is correct