oj.uz

Submission #668504

# Submission time Handle Problem Language Result Execution time Memory
668504 2022-12-04T02:08:32 Z Doxeno Sirni (COCI17_sirni) C++17
140 / 140
 3183 ms 538840 KB 
#include <algorithm>
#include <bits/stdc++.h>
#include <functional>
#include <numeric>
#include <utility>
 
using namespace std;
vector<int> dad, sz;
inline int find(int a){
    if(dad[a] != a){
        dad[a] = find(dad[a]);
    }
    return dad[a];
}
inline bool uni (int a, int b){
    a = find(a);
    b = find(b);
    if(a == b)return 0;
    if(sz[a] < sz[b])swap(a,b);
    dad[b] = a;
    sz[a] += sz[b];
    return 1;
}

int main(){
    int N;
    cin >> N;
    set<int> s;
    int a;
 
    for(int i = 0; i < N; ++i){
        cin >> a;
        s.insert(a);
    }
    N = s.size();
    vector<int> v;
    for(auto x: s)v.emplace_back(x);
 
    long long ans = 0;
    const int m = 1e7+1;
    vector<vector<pair<int, int>>> eg(m);
 
    for(int i = 0; i < N; ++i){
        for(int j = v[i]; j <= v.back(); j += v[i]){
            int k = lower_bound(v.begin() + i + 1, v.end(), j) -v.begin();
            if(k < 0 || k >= N || v[k] - j >= v[i])continue;
            eg[v[k] - j].push_back({k, i});
        }
    }
 
 
    dad.resize(N); 
  	sz.assign(N, 1);
    iota(dad.begin(), dad.end(), 0);
 
 
    for(int w = 0; w < m; ++w){
        for(auto [i, j]: eg[w]){
            if(uni(i, j))ans += w;
        }
    }
 
 
 
    cout << ans << endl;
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 235252 KB Output is correct
2 Correct 159 ms 237616 KB Output is correct
3 Correct 122 ms 235392 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 235340 KB Output is correct
2 Correct 541 ms 235836 KB Output is correct
3 Correct 124 ms 235364 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 235332 KB Output is correct
2 Correct 121 ms 235172 KB Output is correct
3 Correct 122 ms 235340 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 250144 KB Output is correct
2 Correct 521 ms 276060 KB Output is correct
3 Correct 315 ms 253692 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 237524 KB Output is correct
2 Correct 288 ms 257532 KB Output is correct
3 Correct 268 ms 249304 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 261532 KB Output is correct
2 Correct 651 ms 291156 KB Output is correct
3 Correct 308 ms 253228 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 240280 KB Output is correct
2 Correct 588 ms 284992 KB Output is correct
3 Correct 301 ms 251940 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 253056 KB Output is correct
2 Correct 2304 ms 447788 KB Output is correct
3 Correct 315 ms 256072 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 253308 KB Output is correct
2 Correct 3183 ms 538840 KB Output is correct
3 Correct 433 ms 259652 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 238552 KB Output is correct
2 Correct 2931 ms 534240 KB Output is correct
3 Correct 319 ms 254576 KB Output is correct