Submission #1260502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260502		wedonttalkanymore	Sirni (COCI17_sirni)	C++20	140 / 140	4801 ms	575980 KiB

sirni

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

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 1e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 16;

int n;
vector <int> a;
int par[N], sz[N];
int fre[10000005];

void makeset() {
    for (int i = 1; i <= n; i++) {
        par[i] = i;
        sz[i] = 1;
    }
}
int find(int u) {
    if (u == par[u]) return u;
    return par[u] = find(par[u]);
}
void join(int u, int v) {
    u = find(u), v = find(v);
    if (u != v) {
        if (sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        par[v] = u;
    }
}

struct item {
    int u, v, w;
};
vector<item> edge;
bool cmp(item a, item b) {
    return a.w < b.w;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    a.assign(n + 5, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    n = (int)a.size() - 1;
    if (n <= 1) {
        cout << 0;
        return 0;
    }
    int maxA = a[n];
    vector<int> cnt(maxA + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int mul = a[i]; mul <= maxA; mul += a[i]) {
            int pos;
            if (mul == a[i]) pos = upper_bound(a.begin() + 1, a.begin() + n + 1, mul) - a.begin();
            else pos = lower_bound(a.begin() + 1, a.begin() + n + 1, mul) - a.begin();
            if (pos <= n) {
                int w = (int)(a[pos] % a[i]);
                cnt[w]++;
            }
        }
    }
    long long total = 0;
    vector<int> start(maxA + 2, 0);
    for (int w = 0; w <= maxA; w++) {
        start[w] = (int)total;
        total += cnt[w];
    }
    if (total == 0) {
        cout << 0;
        return 0;
    }
    vector<int32_t> eu((size_t)total), ev((size_t)total);
    for (int w = 0; w <= maxA; w++) cnt[w] = 0;
    for (int i = 1; i <= n; i++) {
        for (int mul = a[i]; mul <= maxA; mul += a[i]) {
            int pos;
            if (mul == a[i]) pos = upper_bound(a.begin() + 1, a.begin() + n + 1, mul) - a.begin();
            else pos = lower_bound(a.begin() + 1, a.begin() + n + 1, mul) - a.begin();
            if (pos <= n) {
                int w = (int)(a[pos] % a[i]);
                int p = start[w] + cnt[w];
                eu[p] = (int32_t)i;
                ev[p] = (int32_t)pos;
                cnt[w]++;
            }
        }
    }
    makeset();
    long long ans = 0;
    for (int w = 0; w <= maxA; w++) {
        int s = start[w];
        int e = (w == maxA ? (int)total : start[w + 1]);
        for (int i = s; i < e; i++) {
            int u = eu[i], v = ev[i];
            if (find(u) != find(v)) {
                join(u, v);
                ans += w;
            }
        }
    }
    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