oj.uz

Submission #467148

# Submission time Handle Problem Language Result Execution time Memory
467148 2021-08-21T19:32:39 Z rainliofficial Sirni (COCI17_sirni) C++17
84 / 140
 3473 ms 786436 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct DSU{
    int n;
    vector<int> parent;
    vector<int> sz;
    void init(int nn){
        n = nn;
        parent.resize(n);
        sz.resize(n);
        for (int i=0; i<n; i++){
            parent[i] = i;
            sz[i] = 1;
        }
    }
 
    int find(int a){
        if (parent[a] == a){
            return a;
        }
        return parent[a] = find(parent[a]); // Path compression
    }
 
    void join(int a, int b){
        a = find(a);
        b = find(b);
        if (a == b){
            // Same component
            return;
        }
        if (sz[a] < sz[b]){
            // Point a to b
            parent[a] = b;
            sz[b] += sz[a];
        }else{
            // Point b to a
            parent[b] = a;
            sz[a] += sz[b];
        }
    }
};

const int MAXN = 1e5 + 5, MAXM = 1e7 + 5;
int arr[MAXN];
vector<array<int, 3>> edges;
int n, maxM = 0;

int bs(int target){
    int low = 0;
    int high = n-1;
    while (low < high){
        int mid = (low + high)/2;
        if (arr[mid] >= target){
            high = mid;
        }else{
            low = mid+1;
        }
    }
    if (arr[low] < target){
        return -1;
    }
    return arr[low];
}
void findMultiples(int base){
    int k = 1;
    while (base*k <= maxM){
        if (k == 1){
            int val = bs(base*k+1);
            if (val != -1){
                edges.push_back({base, val, val % base}); 
            }
        }else{
            int val = bs(base*k);
            if (val != -1){
                edges.push_back({base, val, val % base}); 
            }
        }
        k++;
    }
}
bool cmp(array<int, 3> a, array<int, 3> b){
    return a[2] < b[2];
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    //freopen("file.in", "r", stdin);
    //freopen("Sirni.out", "w", stdout);
    cin >> n;
    for (int i=0; i<n; i++){
        cin >> arr[i];
        maxM = max(maxM, arr[i]);
    }
    sort(arr, arr + n);
    int prev = -1;
    map<int, int> mapping;
    int ind = 0;
    for (int i : arr){
        if (i > prev){
            findMultiples(i);
            mapping.insert({i, ind++});
            prev = i;
        }
    }
    sort(edges.begin(), edges.end(), cmp);
    DSU dsu;
    dsu.init(ind);
    int ans = 0;
    for (auto curr : edges){
        if (dsu.find(mapping[curr[0]]) != dsu.find(mapping[curr[1]])){
            dsu.join(mapping[curr[0]], mapping[curr[1]]);
            ans += curr[2];
        }
    }
    cout << ans << "\n";
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 581 ms 49684 KB Output is correct
3 Correct 7 ms 780 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Runtime error 1488 ms 786436 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 3 ms 460 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 5 ms 576 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 29668 KB Output is correct
2 Correct 2607 ms 55028 KB Output is correct
3 Correct 1097 ms 51188 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 3648 KB Output is correct
2 Correct 1154 ms 50648 KB Output is correct
3 Correct 657 ms 28092 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1528 ms 50744 KB Output is correct
2 Correct 3473 ms 99656 KB Output is correct
3 Correct 1002 ms 28796 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 6952 KB Output is correct
2 Correct 3377 ms 99604 KB Output is correct
3 Correct 1062 ms 29616 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1063 ms 25820 KB Output is correct
2 Runtime error 2678 ms 786436 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 1120 ms 28152 KB Output is correct
2 Runtime error 2508 ms 786436 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 121 ms 3816 KB Output is correct
2 Runtime error 3120 ms 786436 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -