oj.uz

Submission #972955

# Submission time Handle Problem Language Result Execution time Memory
972955 2024-05-01T10:44:58 Z TahirAliyev Sirni (COCI17_sirni) C++17
140 / 140
 1691 ms 575712 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define oo 1e9
#define pii pair<int, int>
#define ll long long
#define all(v) v.rbegin(), v.rend()
 
int n, k, m;
const int MAX = 1e5 + 5, MOD = 998244353;
 
int arr[MAX];
 
struct DSU{
    int par[MAX];
    void init(){
        for(int i = 1; i <= n; i++) par[i] = -1;
    } 
    int get(int node){
        if(par[node] < 0) return node;
        return get(par[node]);
    }
    bool unite(int u, int v){
        u = get(u), v = get(v);
        if(u == v) return 0;
        if(-par[u] < -par[v]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
        return 1;
    }
};
 
DSU dsu;
int nxt[int(1e7 + 7)];
vector<pii> E[int(1e7 + 7)];
 
void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    sort(arr + 1, arr + n + 1);
    dsu.init();
    int pos = 1;
    for(int i = 1; i <= 1e7; i++){
        while(arr[pos] < i){
            pos++;
            if(pos == n + 1) break;
        }
        if(pos == n + 1) break;
        nxt[i] = pos;
    }
    for(int i = 1; i <= n; i++){
        if(arr[i] == arr[i - 1]) continue;
        for(int j = arr[i]; j <= 1e7; j += arr[i]){
            int nx = nxt[j + (j == arr[i])];
            if(nx && arr[nx] < j + arr[i]){
                E[arr[nx] - j].push_back({i, nx});
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i <= 1e7; i++){
        for(auto a : E[i]){
            if(dsu.unite(a.first, a.second)) ans += i;
        }
    }   
    cout << ans << '\n';
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while(t--) solve();
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 274512 KB Output is correct
2 Correct 135 ms 276552 KB Output is correct
3 Correct 92 ms 274512 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 236760 KB Output is correct
2 Correct 404 ms 275056 KB Output is correct
3 Correct 92 ms 274552 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 274564 KB Output is correct
2 Correct 89 ms 274260 KB Output is correct
3 Correct 94 ms 274616 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 251016 KB Output is correct
2 Correct 243 ms 283144 KB Output is correct
3 Correct 177 ms 256112 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 242472 KB Output is correct
2 Correct 213 ms 263504 KB Output is correct
3 Correct 133 ms 249196 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 263152 KB Output is correct
2 Correct 283 ms 293904 KB Output is correct
3 Correct 153 ms 254384 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 240024 KB Output is correct
2 Correct 289 ms 287628 KB Output is correct
3 Correct 140 ms 254024 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 287060 KB Output is correct
2 Correct 898 ms 490536 KB Output is correct
3 Correct 176 ms 290336 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 286764 KB Output is correct
2 Correct 1420 ms 575712 KB Output is correct
3 Correct 215 ms 293944 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 276556 KB Output is correct
2 Correct 1691 ms 569996 KB Output is correct
3 Correct 144 ms 255984 KB Output is correct