Submission #1214811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214811		vanea	Sirni (COCI17_sirni)	C++20	84 / 140	4719 ms	828348 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxN = 1e5+10;

int par[mxN];

int get(int x) {
    return par[x] < 0 ? x : par[x] = get(par[x]);
}

bool uni(int a, int b) {
    a = get(a); b = get(b);
    if(a == b) return false;
    par[a] += par[b];
    par[b] = a;
    return true;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> p(n);
    for(int i = 0; i < n; i++) {
        cin >> p[i];
        par[i] = -1;
    }
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    vector<array<int, 3>> edge_list;
    int mx = p.back();
    vector<int> next_largest(mx+1, -1);
    for(int i = 0; i < p.size(); i++) {
        next_largest[p[i]] = i;
    }
    for(int i = mx-1; i >= 0; i--) {
        if(next_largest[i] == -1) {
            next_largest[i] = next_largest[i+1];
        }
    }
    for(int i = 0; i < p.size()-1; i++) {
        int k = p[i];
        edge_list.push_back({p[i+1]%p[i], i, i+1});
        for(int j = 2*k; j <= mx; j += k) {
            int nxt = next_largest[j];
            edge_list.push_back({p[nxt]%k, nxt, i});
        }
    }
    sort(edge_list.begin(), edge_list.end(), [&](array<int, 3> a, array<int, 3> b) {
        return a[0] < b[0];
    });
    int ans = 0;
    for(auto [it, a, b] : edge_list) {
        if(uni(a, b)) ans += it;
    }
    cout << ans;
    return 0;
}

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