oj.uz

Submission #1010896

# Submission time Handle Problem Language Result Execution time Memory
1010896 2024-06-29T13:54:22 Z overwatch9 Sirni (COCI17_sirni) C++17
140 / 140
 955 ms 747792 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
    vector <int> link, sz;
    DSU (int s) {
        link = sz = vector <int> (s+1);
        for (int i = 0; i <= s; i++) {
            link[i] = i;
            sz[i] = 1;
        }
    }
    int head(int x) {
        if (x == link[x])
            return x;
        return link[x] = head(link[x]);
    }
    bool same(int a, int b) {
        return head(a) == head(b);
    }
    void unite(int a, int b) {
        a = head(a);
        b = head(b);
        if (sz[a] < sz[b])
            swap(a, b);
        sz[a] += b;
        link[b] = a;
    }
};
const int maxp = 1e7 + 1;
int nxt[maxp];
vector <array <int, 3>> costs;
vector <pair <int, int>> edges[maxp];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector <int> nums(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    int mx = nums.back();
    fill(nxt, nxt + mx + 1, -1);
    n = nums.size();
    for (int i = 0; i < n; i++)
        nxt[nums[i]] = i;
    for (int i = 0; i < n; i++) {
        for (int j = nums[i]-1; j >= 0 && nxt[j] == -1; j--)
            nxt[j] = nxt[j+1];
    }
    for (int j = mx; j >= nums.back(); j--)
        nxt[j] = n-1;
    for (int i = 0; i < n; i++) {
        if (i+1 < n)
            edges[nums[i+1] % nums[i]].push_back({i, i+1});
        for (int j = nums[i]; j <= mx; j += nums[i]) {
            edges[nums[nxt[j]] % nums[i]].push_back({i, nxt[j]});
        }
    }
    
    ll ans = 0;
    DSU dsu(n+1);
    for (int i = 0, cnt = 0; cnt < n-1 && i <= mx; i++) {
        for (auto j : edges[i]) {
            if (!dsu.same(j.first, j.second)) {
                dsu.unite(j.first, j.second);
                ans += i;
                cnt++;
            }
            if (cnt == n-1)
                break;
        }
    }
    cout << ans << '\n';
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 274380 KB Output is correct
2 Correct 138 ms 303700 KB Output is correct
3 Correct 90 ms 274716 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 236632 KB Output is correct
2 Correct 652 ms 669040 KB Output is correct
3 Correct 88 ms 275028 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 274492 KB Output is correct
2 Correct 88 ms 274256 KB Output is correct
3 Correct 87 ms 274652 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 251012 KB Output is correct
2 Correct 163 ms 278984 KB Output is correct
3 Correct 113 ms 263228 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 241488 KB Output is correct
2 Correct 113 ms 263120 KB Output is correct
3 Correct 97 ms 249128 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 263152 KB Output is correct
2 Correct 155 ms 296140 KB Output is correct
3 Correct 109 ms 259512 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 240836 KB Output is correct
2 Correct 156 ms 296728 KB Output is correct
3 Correct 114 ms 261088 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 289732 KB Output is correct
2 Correct 683 ms 633996 KB Output is correct
3 Correct 150 ms 292624 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 294244 KB Output is correct
2 Correct 955 ms 747792 KB Output is correct
3 Correct 243 ms 348568 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 277196 KB Output is correct
2 Correct 796 ms 635380 KB Output is correct
3 Correct 112 ms 264772 KB Output is correct