Submission #1207091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207091		racsosabe	Sirni (COCI17_sirni)	C++17	140 / 140	1381 ms	633860 KiB

sirni

#include<bits/stdc++.h>
using namespace::std;

const int N = 100000 + 5;
const int MAX = 10000000 + 2;

int n;
int par[N];
int sizes[N];
int R[MAX];
int who[MAX];
vector<pair<int, int>> edges[MAX];

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

void join(int a, int b) {
    a = get(a);
    b = get(b);
    if(a == b) return;
    if(sizes[a] > sizes[b]) swap(a, b);
    par[a] = b;
    sizes[b] += sizes[a];
}

int get_cost(int x, int y) {
    return min(x % y, y % x);
}

void get_edges(vector<int> &a) {
    int maximum = a.back();
    int at = (int)a.size() - 1;
    int last = -1;
    for(int i = maximum; i >= 1; i--) {
        if(at >= 0 and a[at] == i) {
            who[i] = at;
            int last_taken = -1;
            if(last != last_taken) {
                edges[get_cost(i, last)].emplace_back(i, last);
                last_taken = last;
            }
            for(int l = (i << 1); l <= maximum; l += i) {
                int to = R[l];
                if(to != last_taken) {
                    edges[get_cost(i, to)].emplace_back(i, to);
                    last_taken = to;
                }
            }
            last = i;
            at--;
        }
        R[i] = last;
    }
}

long long solve(vector<int> &a) {
    get_edges(a);
    for(int i = 0; i < n; i++) {
        par[i] = i;
        sizes[i] = 1;
    }
    long long res = 0;
    int maximum = a[n - 1];
    for(int i = 0; i < maximum; i++) {
        for(auto e : edges[i]) {
            int u, v;
            tie(u, v) = e;
            u = who[u], v = who[v];
            if(get(u) != get(v)) {
                res += i;
                join(u, v);
            }
        }
    }
    return res;
}

int main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    n = a.size();
    cout << solve(a) << '\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