oj.uz

Submission #914998

# Submission time Handle Problem Language Result Execution time Memory
914998 2024-01-23T06:22:40 Z Em1L Sirni (COCI17_sirni) C++17
98 / 140
 2043 ms 786432 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using tiiii = tuple<int, int, ll, ll>;

class DSU {
 private:
    int n;
    vector < int > parent, scale;

    int GetRoot(int v) {
        return parent[v] = v == parent[v] ? v : GetRoot(parent[v]);
    }

 public:
    DSU(int n) {
        this->n = n;
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        scale.resize(n, 1);
    }

    bool Unite(int v, int u) {
        v = GetRoot(v), u = GetRoot(u);

        if (v == u)
            return false;

        if (scale[v] < scale[u])
            swap(v, u);

        parent[u] = v;
        scale[v] += scale[u];

        return true;
    }
};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    const int P = 1e+7;

    int n; cin >> n;

    vector < int > p(n);

    for (int i = 0; i < n; i++)
        cin >> p[i];

    sort(p.begin(), p.end()); p.erase(unique(p.begin(), p.end()), p.end());

    n = p.size();

    vector < int > nextGreater(P + 1, -1);

    for (int i = 0; i < n; i++)
        nextGreater[p[i]] = i;

    for (int i = P; i >= 1; i--)
        if (nextGreater[i] == -1)
            nextGreater[i] = nextGreater[i + 1];

    vector < vector < pii > > edge(P + 1);

    for (int i = 0; i < n; i++) {
        if (i < n - 1)
            edge[p[i + 1] % p[i]].push_back({ i, i + 1 });

        for (int x = 2 * p[i]; x <= P; x += p[i]) {
            int j = nextGreater[x];

            if (j != -1)
                edge[p[j] % p[i]].push_back({ i, j });
        }
    }

    ll ans = 0;

    DSU dsu(n);

    for (int c = 0; c <= P; c++)
        for (auto [i, j] : edge[c])
            if (dsu.Unite(i, j))
                ans += c;

    cout << ans << "\n";
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 274516 KB Output is correct
2 Correct 222 ms 303960 KB Output is correct
3 Correct 156 ms 274824 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 347840 KB Output is correct
2 Correct 1134 ms 669988 KB Output is correct
3 Correct 179 ms 275036 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 274512 KB Output is correct
2 Correct 154 ms 274256 KB Output is correct
3 Correct 155 ms 274764 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 424856 KB Output is correct
2 Runtime error 1110 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 299084 KB Output is correct
2 Correct 1285 ms 557780 KB Output is correct
3 Correct 999 ms 567040 KB Output is correct

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1107 ms 563892 KB Output is correct
2 Runtime error 884 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 897 ms 567916 KB Output is correct
2 Runtime error 891 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 289380 KB Output is correct
2 Correct 1158 ms 633280 KB Output is correct
3 Correct 213 ms 291996 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 293344 KB Output is correct
2 Correct 2043 ms 753552 KB Output is correct
3 Correct 328 ms 350152 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 277056 KB Output is correct
2 Correct 1926 ms 636984 KB Output is correct
3 Correct 779 ms 481620 KB Output is correct