Submission #1207070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207070		racsosabe	Sirni (COCI17_sirni)	C++17	0 / 140	850 ms	8240 KiB

sirni

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

const int N = 100000 + 5;

int n;
int e;
int par[N];
int sizes[N];
map<int, int> avail;
int to[N];
int nxt[N];
int last[N];
int best_cost[N];
int best_edge[N];

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];
}

void add_edge(int u, int v) {
    to[e] = v;
    nxt[e] = last[u];
    last[u] = e++;
}

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

void get_light_edge(int x, vector<int> &a) {
    for(int edge = last[x]; ~edge; edge = nxt[edge]) {
        int at = to[edge];
        avail.erase(a[at]);
    }
    int maxi = (*avail.rbegin()).first;
    for(int edge = last[x]; ~edge; edge = nxt[edge]) {
        int at = to[edge];
        int p = a[at];
        //cout << "Looking to minimize for " << p << endl;
        for(int i = p; i <= maxi; ) {
            int which, where;
            tie(which, where) = *avail.lower_bound(i);
            //cout << "Which: " << which << endl;
            //cout << "Where: " << where << endl;
            int cur_cost = get_cost(which, p);
            //cout << "Cost: " << cur_cost << endl;
            if(cur_cost < best_cost[where]) {
                best_cost[where] = cur_cost;
                best_edge[where] = at;
            }
            if(cur_cost < best_cost[at]) {
                best_cost[at] = cur_cost;
                best_edge[at] = at;
            }
            if(which % p == 0) {
                i = which + p;
            }
            else {
                i = which + p - which % p;
            }
        }
    }
    for(int edge = last[x]; ~edge; edge = nxt[edge]) {
        int at = to[edge];
        avail[a[at]] = at;
    }
}

long long solve(vector<int> &a) {
    for(int i = 0; i < n; i++) {
        avail[a[i]] = i;
        par[i] = i;
        sizes[i] = 1;
        //cout << a[i] << " ";
    }
    //cout << endl;
    long long res = 0;
    while(sizes[get(0)] < n) {
        //cout << "New iteration" << endl;
        e = 0;
        fill(last, last + n, -1);
        for(int i = 0; i < n; i++) {
            add_edge(get(i), i);
            best_cost[i] = INT_MAX;
            best_edge[i] = -1;
        }
        for(int i = 0; i < n; i++) {
            if(par[i] == i) {
                get_light_edge(i, a);
            }
        }
        for(int u = 0; u < n; u++) {
            int v = best_edge[u];
            assert(~v);
            if(v == -1) continue;
            if(get(u) != get(v)) {
                res += get_cost(a[u], a[v]);
                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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14