oj.uz

Submission #972951

# Submission time Handle Problem Language Result Execution time Memory
972951 2024-05-01T10:39:48 Z TahirAliyev Sirni (COCI17_sirni) C++17
84 / 140
 1070 ms 786432 KB 
#include <bits/stdc++.h>

using namespace std;

#define oo 1e9
#define int long long
#define pii pair<int, int>
#define all(v) v.rbegin(), v.rend()

int n, k, m;
const int MAX = 1e5 + 5, MOD = 998244353, MX = 1e7 + 7;

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[MX];
vector<pii> E[MX];

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});
            }
        }
    }
    int 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';
}

signed 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 110 ms 314532 KB Output is correct
2 Correct 358 ms 378292 KB Output is correct
3 Correct 94 ms 315008 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 238932 KB Output is correct
2 Runtime error 961 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 91 ms 314704 KB Output is correct
2 Correct 92 ms 314648 KB Output is correct
3 Correct 92 ms 314824 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 267364 KB Output is correct
2 Correct 293 ms 333556 KB Output is correct
3 Correct 187 ms 296188 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 250872 KB Output is correct
2 Correct 243 ms 293668 KB Output is correct
3 Correct 159 ms 263908 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 295888 KB Output is correct
2 Correct 357 ms 369740 KB Output is correct
3 Correct 177 ms 289320 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 247832 KB Output is correct
2 Correct 434 ms 376744 KB Output is correct
3 Correct 180 ms 296452 KB Output is correct

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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