Submission #1286378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286378		tab1540	Sirni (COCI17_sirni)	C++20	0 / 140	147 ms	85648 KiB

sirni

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x<y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x>y) return x = y, true; else return false;}

const int maxn = 1e5 + 5;
const int max_edges_size = 1e7 + 9;
const int maxval = 1e7 + 5;

int n;
int ma;
vector<int> a;
pair<pair<int, int>, int> edges[max_edges_size], sorted_edges[max_edges_size];
int par[maxn], sz[maxn];
int nxt[maxval], cnt[maxval];

int root (int u) {
    return ((par[u] == u) ? u : (par[u] = root(par[u])) );
}

bool join (int u, int v) {
    u = root(u);
    v = root(v);

    if (u == v)
        return false;

    if (sz[u] < sz[v])
        swap (u, v);

    par[v] = u;
    sz[u] += sz[v];

    return true;
}

void countingSortEdges(int m) {
    if (m <= 0) {
        return;
    }
    for (int i = 1; i <= m; ++i) {
        cnt[edges[i].second]++;
    }

    for (int i = 1; i <= ma; ++i) {
        cnt[i] += cnt[i - 1];
    }

    int key, post_pos;
    for (int i = m; i >= 1; --i) {
        key = edges[i].second;
        
        post_pos = cnt[key];
        
        sorted_edges[post_pos] = edges[i];
        
        cnt[key]--;
    }

    for (int i = 1; i <= m; ++i) {
        edges[i] = sorted_edges[i];
    }
}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    a.resize(n);

    ma = 0;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        maximize(ma, a[i]);
    }

    fill_n (&nxt[0], maxval, -1);
    sort (a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    n = a.size();
    for (int i = 0; i < n; ++i) {
        nxt[a[i]] = i;
        
        par[i] = i;
        sz[i] = 1;
    }

    for (int i = ma; i >= 0; --i)
        if (nxt[i] == -1)
            nxt[i] = nxt[i + 1];

    int u, w, minw;
    int pre = -1;
    int m = 0;

    for (int i = 0; i < a.size(); ++i) {
        minw = 1e7;

        for (int k = 0; k * a[i] <= ma; ++k) {
            u = nxt[k * a[i] + (k == 1)];

            
            if (u != -1 && u != pre) {
                w = min(a[i] % a[u], a[u] % a[i]);
                if (w < minw) {
                    edges[++m] = (pair<pair<int, int>, int>(pair<int, int>(i, u), w));
                    minw = w;

                    cout << i << ' ' << u << ' ' << w << '\n';
                }
                // cout << i << ' ' << u << ' ' << w << '\n';
                pre = u;
            }
        }
    }
    countingSortEdges(m);

    int v;
    long long ans = 0;

    for (int i = 1; i <= m; ++i) {
        const pair<pair<int, int>, int>& edge = edges[i];
        u = edge.first.first;
        v = edge.first.second;
        w = edge.second;
        
        ans += (long long)w * (long long)join(u, v);
    }

    cout << ans;
    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