Submission #503520

#	Time	Username	Problem	Language	Result	Execution time	Memory
503520		hoanghq2004	Sirni (COCI17_sirni)	C++14	140 / 140	3131 ms	440132 KiB

sirni

#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int Nmax = 1e5 + 10;

int n, a[Nmax];
int root[Nmax], sz[Nmax];
int near[10000010];

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

int comp;
long long cost = 0;

inline int Union(int u, int v, int w) {
    if ((u = Find(u)) == (v = Find(v)))
        return 0;
    if (sz[u] < sz[v])
        swap(u, v);
    sz[u] += sz[v];
    root[v] = u;
    --comp;
    cost += w;
    if (comp == 1) {
        cout << cost << "\n";
        exit(0);
    }
    return 1;
}

vector<pair<int, int> > e[10000010];

int main() {
    ios ::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);
    n = unique(a + 1, a + n + 1) - a - 1;
    comp = n;
    for (int i = 1; i <= n; ++i) near[a[i]] = i;
    for (int i = a[n]; i >= 0; --i)
        if (!near[i])
            near[i] = near[i + 1];

    for (int i = 1; i <= n; ++i) root[i] = i, sz[i] = 1;
    for (int i = 1; i <= n; ++i) {
        if (i + 1 <= n)
            e[a[i + 1] % a[i]].push_back({ i, i + 1 });
        for (int j = a[i] * 2; j <= a[n]; j += a[i]) {
            int t = near[j];
            if (a[t] - j >= a[i])
                continue;
            if (Find(t) == Find(i))
                continue;
            if (a[t] == j)
                Union(i, t, 0);
            else
                e[a[t] - j].push_back({ i, t });
        }
    }
    //    cout << e.size() << "\n";
    for (int i = 1; i <= a[n]; ++i) {
        for (auto [u, v] : e[i]) Union(u, v, i);
    }
}

Compilation message (stderr)

sirni.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
sirni.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
sirni.cpp: In function 'int main()':
sirni.cpp:74:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |         for (auto [u, v] : e[i]) Union(u, v, i);
      |                   ^

• 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