oj.uz

Submission #889311

# Submission time Handle Problem Language Result Execution time Memory
889311 2023-12-19T10:37:36 Z dimashhh Sirni (COCI17_sirni) C++17
140 / 140
 3106 ms 769192 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1, MOD = 998244353,MAX = 1e7 + 1;
typedef long long ll;

int n,a[N],p[MAX];
vector<ll> b;
vector<pair<int,int>> g[MAX];
int get(int v){
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
void merge(int v,int u){
    v = get(v);
    u = get(u);
    p[v] = u;
}
void add(int x){
    for(int i = 0;true;i++){
        if(i * x > b.back()) break;
        int it = lower_bound(b.begin(),b.end(),x * i) - b.begin();
        if(b[it] == x) it++;
        if(it < (int)b.size()){
            int val = min(b[it] % x,x % b[it]);
            // cout << val << ' ' << x << ' ' << b[it] << '\n';
            g[val].push_back({x,b[it]});
        }
    }
}
void test(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for(int i = 1;i < MAX;i++){
        p[i] = i;
    }
    sort(a + 1,a + n + 1);
    for(int i = 1;i <= n;i++){
        if(a[i] != a[i - 1]){
            b.push_back(a[i]);
        }
    }
    for(auto i:b){
        add(i);
    }
    ll ans = 0;
    for(int i = 0;i < MAX;i++){
        for(auto [x,y]:g[i]){
            if(get(x) != get(y)){
                ans += i;
                merge(x,y);
            }
        }
    }
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1; // cin >> T;
    while (T--)
        test();
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 275540 KB Output is correct
2 Correct 167 ms 304984 KB Output is correct
3 Correct 88 ms 275796 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 275720 KB Output is correct
2 Correct 1066 ms 685576 KB Output is correct
3 Correct 85 ms 276304 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 275616 KB Output is correct
2 Correct 82 ms 275452 KB Output is correct
3 Correct 85 ms 275980 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 289504 KB Output is correct
2 Correct 453 ms 321744 KB Output is correct
3 Correct 240 ms 299700 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 278032 KB Output is correct
2 Correct 223 ms 299092 KB Output is correct
3 Correct 186 ms 288664 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 299016 KB Output is correct
2 Correct 541 ms 335804 KB Output is correct
3 Correct 226 ms 296680 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 280528 KB Output is correct
2 Correct 507 ms 335132 KB Output is correct
3 Correct 227 ms 300988 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 291164 KB Output is correct
2 Correct 2263 ms 660620 KB Output is correct
3 Correct 246 ms 294860 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 297780 KB Output is correct
2 Correct 3106 ms 769192 KB Output is correct
3 Correct 433 ms 351652 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 278412 KB Output is correct
2 Correct 2563 ms 638592 KB Output is correct
3 Correct 242 ms 300056 KB Output is correct