Submission #1167674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167674		Turkhuu	Sirni (COCI17_sirni)	C++20	126 / 140	1374 ms	843164 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;
struct DSU {
    int n, comp; vector<int> a;
    DSU(int n = 0) : n(n), comp(n), a(n, -1) {}
    int operator[](int x) {return find(x);}
    int find(int x) {return a[x] < 0 ? x : a[x] = find(a[x]);}
    int size(int x) {return -a[find(x)];}
    bool same(int a, int b) {return find(a) == find(b);}
    int unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return x;
        if (a[x] > a[y]) swap(x, y);
        return comp--, a[x] += a[y], a[y] = x;
    }
};
const int N = 1e7;
int nxt[N + 1];
vector<array<int, 2>> edges[N];
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();
        }
    }
    DSU dsu(n + 1);
    ll ans = 0;
    FOR(i, 0, n - 1) {
        for (auto [x, y] : edges[i]) {
            if (!dsu.same(x, y)) {
                ans += i;
                dsu.unite(x, y);
            }
        }
    }
    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