oj.uz

Submission #503520

# Submission time Handle Problem Language Result Execution time Memory
503520 2022-01-08T09:40:22 Z hoanghq2004 Sirni (COCI17_sirni) C++14
140 / 140
 3131 ms 440132 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 274420 KB Output is correct
2 Correct 190 ms 276608 KB Output is correct
3 Correct 152 ms 274436 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 235172 KB Output is correct
2 Correct 340 ms 274280 KB Output is correct
3 Correct 153 ms 274436 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 274460 KB Output is correct
2 Correct 153 ms 274208 KB Output is correct
3 Correct 153 ms 274384 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 248140 KB Output is correct
2 Correct 209 ms 254784 KB Output is correct
3 Correct 169 ms 251196 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 240884 KB Output is correct
2 Correct 213 ms 259676 KB Output is correct
3 Correct 148 ms 244928 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 253680 KB Output is correct
2 Correct 211 ms 250864 KB Output is correct
3 Correct 163 ms 248076 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 238460 KB Output is correct
2 Correct 216 ms 251236 KB Output is correct
3 Correct 167 ms 249056 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 287916 KB Output is correct
2 Correct 992 ms 326872 KB Output is correct
3 Correct 276 ms 290336 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 287372 KB Output is correct
2 Correct 2499 ms 345648 KB Output is correct
3 Correct 316 ms 293308 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 276828 KB Output is correct
2 Correct 3131 ms 440132 KB Output is correct
3 Correct 195 ms 249912 KB Output is correct