Submission #1138547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138547		buzdi	Sirni (COCI17_sirni)	C++17	140 / 140	1457 ms	746908 KiB

sirni

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define ll long long
#define ld long double

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int NMAX = 1e5;
const int VMAX = 1e7;

struct DSU {
    int parent[NMAX + 1];
    int sz[NMAX + 1];

    void Initialize(int n) {
        for(int i = 1; i <= n; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    int GetRoot(int node) {
        return parent[node] = (parent[node] == node ? node : GetRoot(parent[node]));
    }

    bool Unite(int x, int y) {
        int root_x = GetRoot(x);
        int root_y = GetRoot(y);
        if(root_x == root_y) {
            return false;
        }
        if(sz[root_x] > sz[root_y]) {
            swap(root_x, root_y);
        }
        sz[root_y] += sz[root_x];
        parent[root_x] = root_y;
        return true;
    }
}dsu;

int n, m, k, ind, max_value;
ll answer;
int a[NMAX + 1];
int next_greater[VMAX + 1];
vector<pair<int, int>> edges[VMAX + 1];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    ind = 1;
    for(int i = 2; i <= n; i++) {
        if(a[i] != a[i - 1]) {
            a[++ind] = a[i];
        }
    }
    n = ind;

    max_value = a[n];
    for(int i = 1; i <= n; i++) {
        next_greater[a[i]] = i;
    }
    for(int i = max_value - 1; i >= 1; i--) {
        if(!next_greater[i]) {
            next_greater[i] = next_greater[i + 1];
        }
    }

    // for(int i = 1; i <= max_value; i++) {
    //     cout << next_greater[i] << ' ';
    // }
    // cout << '\n';

    for(int i = 1; i < n; i++) {
        edges[a[i + 1] % a[i]].push_back({i, i + 1});
        for(int j = 2 * a[i]; j <= max_value; j += a[i]) {
            int closest = next_greater[j];
            edges[a[closest] % a[i]].push_back({i, closest});
        }
    }

    dsu.Initialize(n);
    for(int i = 0; i <= max_value; i++) {
        for(auto [a, b] : edges[i]) {
            if(dsu.Unite(a, b)) {
                answer += i;
            }
        }
    }
    cout << answer << '\n';

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14