oj.uz

Submission #889312

# Submission time Handle Problem Language Result Execution time Memory
889312 2023-12-19T10:38:10 Z dimashhh Sirni (COCI17_sirni) C++17
0 / 140
 316 ms 300352 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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 275540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 275540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 275620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 288200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 278096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 316 ms 300352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 280572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 221 ms 290812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 298176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 278228 KB Output isn't correct
2 Halted 0 ms 0 KB -