oj.uz

Submission #972946

# Submission time Handle Problem Language Result Execution time Memory
972946 2024-05-01T10:36:42 Z TahirAliyev Sirni (COCI17_sirni) C++17
112 / 140
 2791 ms 786432 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){
                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 175 ms 274512 KB Output is correct
2 Correct 393 ms 307040 KB Output is correct
3 Correct 149 ms 274520 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 235456 KB Output is correct
2 Runtime error 2791 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 274504 KB Output is correct
2 Correct 162 ms 274396 KB Output is correct
3 Correct 228 ms 274508 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 250296 KB Output is correct
2 Correct 257 ms 279848 KB Output is correct
3 Correct 216 ms 262732 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 241380 KB Output is correct
2 Correct 227 ms 264328 KB Output is correct
3 Correct 184 ms 248520 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 263064 KB Output is correct
2 Correct 328 ms 299556 KB Output is correct
3 Correct 220 ms 258976 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 240024 KB Output is correct
2 Correct 371 ms 301344 KB Output is correct
3 Correct 214 ms 261916 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 289304 KB Output is correct
2 Correct 1192 ms 634692 KB Output is correct
3 Correct 167 ms 292088 KB Output is correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 293688 KB Output is correct
2 Runtime error 1981 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 276772 KB Output is correct
2 Correct 2005 ms 657556 KB Output is correct
3 Correct 197 ms 262796 KB Output is correct