Submission #1167688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167688		Turkhuu	Sirni (COCI17_sirni)	C++20	126 / 140	1452 ms	843236 KiB

sirni

#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
const int N = 1e7;
int nxt[N + 1], a[N + 1];
vector<array<int, 2>> edges[N];
int find(int x) {
    return a[x] < 0 ? x : a[x] = find(a[x]);
}
void solve() {
    int m, n = 0;
    cin >> m;
    vector<int> p(m);
    for (int& i : p) {
        cin >> i;
        n = max(n, i);
    }
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    m = p.size();
    ROF(i, n, 1) {
        nxt[i] = nxt[i + 1];
        if (!p.empty() && i == p.back()) {
            for (int j = i; j <= n; j += i) {
                if (nxt[j]) {
                    edges[nxt[j] % i].push_back({i, nxt[j]});
                }
            }
            nxt[i] = i;
            p.pop_back();
        }
    }
    memset(a, -1, n * sizeof(int));
    int comp = m;
    ll ans = 0;
    FOR(i, 0, i) {
        for (auto [x, y] : edges[i]) {
            int _x = find(x), _y = find(y);
            if (_x != _y) {
                if (a[_x] > a[_y]) swap(_x, _y);
                a[_x] += a[_y], a[_y] = _x;
                ans += i;
                if (--comp == 1) {
                    cout << ans;
                    return;
                }
            }
        }
    }
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 6/22;
}

• 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: 0 / 14
• Subtask 10: 14 / 14