Submission #1267647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267647		ducdev	Sirni (COCI17_sirni)	C++20	140 / 140	2638 ms	473876 KiB

sirni

// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()

typedef long long ll;

const int MAX_N = 1e5;
const int MAX_V = 1e7;
const int MOD = 1e9 + 7;

struct Edge {
    int u, v, w;
    Edge() {};
    Edge(int u, int v, int w) : u(u), v(v), w(w) {};

    bool operator<(const Edge &other) const {
        return w < other.w;
    };
};

struct DSU {
    vector<int> par, sz;
    int n;

    DSU(int n) : n(n) {
        par.resize(n + 1), sz.resize(n + 1);
        for (int u = 1; u <= n; u++) {
            par[u] = u;
            sz[u] = 1;
        };
    };

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

    bool unionSet(int u, int v) {
        u = findSet(u), v = findSet(v);
        if (u == v) return false;

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

        return true;
    };
};

int n;
int a[MAX_N + 5];

namespace SUBTASK_1 {
    const int N = 1000;

    void Solve() {
        DSU DSU(n);

        vector<Edge> edges;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                edges.push_back(Edge(i, j, min(a[i] % a[j], a[j] % a[i])));
            };
        };

        sort(all(edges));

        ll res = 0;
        for (Edge &e : edges) {
            int u = e.u, v = e.v, w = e.w;
            if (DSU.unionSet(u, v)) res += w;
        };

        cout << res << '\n';
    };
};  // namespace SUBTASK_1

namespace SUBTASK_2 {
    const int N = MAX_N;
    const int V = MAX_V;

    int idx[V + 5], nextExist[V + 5];
    bool used[N + 5];

    void Solve() {
        sort(a + 1, a + n + 1);

        DSU DSU(n);
        int numCC = n;
        for (int i = 1; i <= n; i++) {
            idx[a[i]] = i;
            if (a[i] == a[i - 1]) numCC -= DSU.unionSet(i, i - 1);
        };

        int mx = a[n];

        for (int i = 1; i <= mx; i++) {
            if (!idx[i]) continue;
            for (int j = 2 * i; j <= mx; j += i) {
                if (idx[j]) {
                    numCC -= DSU.unionSet(idx[i], idx[j]);
                    idx[j] = idx[i];
                };
            };
        };

        if (numCC == 1) {
            return cout << 0, void();
        };

        nextExist[mx + 1] = mx + 1;
        for (int i = mx; i >= 1; i--) {
            nextExist[i] = nextExist[i + 1];
            if (idx[i]) nextExist[i] = i;
        };

        vector<Edge> edges;

        for (int i = 1; i <= mx; i++) {
            if (!idx[i]) continue;
            int u = idx[i];
            for (int j = i; j <= mx; j += i) {
                int l = j + 1, r = min(j + i - 1, mx);

                if (nextExist[l] <= r) {
                    int v = idx[nextExist[l]];
                    edges.push_back(Edge(u, v, nextExist[l] - j));
                };
            };
        };

        sort(all(edges));

        ll res = 0;
        for (Edge &e : edges) {
            int u = e.u, v = e.v, w = e.w;
            if (DSU.unionSet(u, v)) res += w, numCC--;
            if (numCC == 1) break;
        };

        cout << res << '\n';
    };
};  // namespace SUBTASK_2

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("SIRNI.INP", "r")) {
        freopen("SIRNI.INP", "r", stdin);
        freopen("SIRNI.OUT", "w", stdout);
    };

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    };

    if (n <= 1000)
        return SUBTASK_1::Solve(), 0;
    SUBTASK_2::Solve();
};

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         freopen("SIRNI.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen("SIRNI.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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