Submission #1214812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214812		vanea	Sirni (COCI17_sirni)	C++20	140 / 140	1188 ms	746820 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());
    int mx = p.back();
    vector<vector<array<int, 2>>> edge_list(mx+1);
    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[p[i+1]%p[i]].push_back({i, i+1});
        for(int j = 2*k; j <= mx; j += k) {
            int nxt = next_largest[j];
            edge_list[p[nxt]%k].push_back({nxt, i});
        }
    }
    int ans = 0;
    for(int c = 0; c <= mx; c++) {
        for(auto [a, b] : edge_list[c]) {
            if(uni(a, b)) ans += c;
        }
    }
    cout << ans;
    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