oj.uz

Submission #248368

# Submission time Handle Problem Language Result Execution time Memory
248368 2020-07-12T09:59:45 Z NONAME Sirni (COCI17_sirni) C++14
140 / 140
 3987 ms 681348 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;

const int oo = int(1e7) + 1;
const int N = int(1e5) + 10;

int n, a[N], pr[N];
vector <pair <int, int> > g[oo];

int f(int x) { return (x == pr[x]) ? x : pr[x] = f(pr[x]); }

int main() {
    fast_io;

    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i], pr[i] = i;

    sort(a, a + n);

    for (int i = 0; i < n - 1; ++i) {
        if (a[i] == a[i + 1])
            g[0].push_back(make_pair(i, i + 1));

        for (int j = a[i]; j <= oo; j += a[i]) {
            int p = lower_bound(a, a + n, (j == a[i] ? j + 1 : j)) - a;

            if (p == n)
                break;

            while (j <= a[p])
                j += a[i];

            j -= a[i];
            g[a[p] - j].push_back(make_pair(i, p));
        }
    }

    ll ans = 0;
    int kol = 0;
    for (int i = 0; i < oo; ++i)
    for (auto j : g[i]) {
        int x = f(j.first);
        int y = f(j.second);

        if (x == y)
            continue;

        ans += i;
        ++kol;
        if (kol == n - 1)
            return void(cout << ans << "\n"), 0;
        pr[y] = x;
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 235256 KB Output is correct
2 Correct 139 ms 238056 KB Output is correct
3 Correct 127 ms 235512 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 235328 KB Output is correct
2 Correct 155 ms 236280 KB Output is correct
3 Correct 123 ms 235384 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 235384 KB Output is correct
2 Correct 122 ms 235384 KB Output is correct
3 Correct 123 ms 235384 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 245360 KB Output is correct
2 Correct 654 ms 282372 KB Output is correct
3 Correct 332 ms 255840 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 236792 KB Output is correct
2 Correct 1742 ms 504288 KB Output is correct
3 Correct 275 ms 247468 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 259972 KB Output is correct
2 Correct 938 ms 313156 KB Output is correct
3 Correct 285 ms 250204 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 239448 KB Output is correct
2 Correct 764 ms 303848 KB Output is correct
3 Correct 310 ms 254180 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 247928 KB Output is correct
2 Correct 2701 ms 533480 KB Output is correct
3 Correct 305 ms 250632 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 247884 KB Output is correct
2 Correct 3834 ms 647436 KB Output is correct
3 Correct 344 ms 257168 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 237560 KB Output is correct
2 Correct 3987 ms 681348 KB Output is correct
3 Correct 346 ms 256092 KB Output is correct