oj.uz

Submission #1010855

# Submission time Handle Problem Language Result Execution time Memory
1010855 2024-06-29T12:43:00 Z overwatch9 Sirni (COCI17_sirni) C++17
98 / 140
 5000 ms 406268 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;
    }
};
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());
    DSU dsu(n+1);
    if (n <= 1000) {
        vector <array <int, 3>> mods;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int cost = min(nums[i] % nums[j], nums[j] % nums[i]);
                mods.push_back({cost, i, j});
            }
        }
        sort(mods.begin(), mods.end());
        ll ans = 0;
        int sz = mods.size();
        int cnt = 0;
        for (int i = 0; i < sz && cnt < n-1; i++) {
            if (!dsu.same(mods[i][1], mods[i][2])) {
                ans += mods[i][0];
                dsu.unite(mods[i][1], mods[i][2]);
                cnt++;
            }
        }
        cout << ans << '\n';
    } else {
        multiset <pair <int, int>> nums2;
        unordered_map <int, int> cnt;
        for (int i = 0; i < n; i++) {
            nums2.insert({nums[i], i});
            cnt[nums[i]]++;
        }
        int mx = nums2.rbegin()->first;
        vector <array <int, 3>> costs;
        for (int i = 0; i < n; i++) {
            cnt[nums[i]]--;
            nums2.erase(nums2.find({nums[i], i}));
            if (cnt[nums[i]] >= 1) {
                costs.push_back({0, i, nums2.lower_bound({nums[i], 0})->second});
            } else {
                int lst = 0;
                for (int j = nums[i]; j <= mx; j += nums[i]) {
                    auto it = nums2.lower_bound({j, 0});
                    if (it == nums2.end())
                        break;
                    if (lst != it->first) {
                        costs.push_back({it->first % nums[i], i, it->second});
                        lst = it->first;
                    }
                }
            }
        }
        ll ans = 0;
        int c = 0;
        sort(costs.begin(), costs.end());
        for (auto i : costs) {
            if (!dsu.same(i[1], i[2])) {
                ans += i[0];
                dsu.unite(i[1], i[2]);
                c++;
                if (c == n-1)
                    break;
            }
        }
        cout << ans << '\n';
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 6604 KB Output is correct
2 Correct 61 ms 6604 KB Output is correct
3 Correct 49 ms 6600 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6616 KB Output is correct
2 Correct 64 ms 6600 KB Output is correct
3 Correct 50 ms 6600 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 6604 KB Output is correct
2 Correct 37 ms 6600 KB Output is correct
3 Correct 53 ms 6600 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 24244 KB Output is correct
2 Correct 1176 ms 60624 KB Output is correct
3 Correct 468 ms 34936 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4976 KB Output is correct
2 Correct 454 ms 56388 KB Output is correct
3 Correct 323 ms 34544 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 61304 KB Output is correct
2 Correct 1548 ms 110404 KB Output is correct
3 Correct 412 ms 36512 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 10616 KB Output is correct
2 Correct 1332 ms 108644 KB Output is correct
3 Correct 431 ms 35260 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 36772 KB Output is correct
2 Execution timed out 5070 ms 406268 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 36964 KB Output is correct
2 Execution timed out 5046 ms 404388 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5584 KB Output is correct
2 Execution timed out 5051 ms 404032 KB Time limit exceeded
3 Halted 0 ms 0 KB -