Submission #1273536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273536		vk3601h	Sirni (COCI17_sirni)	C++20	140 / 140	1281 ms	746516 KiB

sirni

#include <bits/stdc++.h>
using namespace std;

class DisjointSet{
private:
    vector<int> parents;
    vector<int> sizes;

public:
    DisjointSet(int size) : parents(size), sizes(size, 1) {
        for (int i = 0; i < size; i++) parents[i] = i;
    }

    int find(int x) {return parents[x] == x ? x : parents[x] = find(parents[x]);}

    bool unite(pair<int, int> edge){
        int x_root = find(edge.first);
        int y_root = find(edge.second);
        if (x_root == y_root) return false;

        if (sizes[x_root] < sizes[y_root]) swap(x_root, y_root);
        parents[y_root] = x_root;
        sizes[x_root] += sizes[y_root];
        return true;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int card_num;
    cin >> card_num;

    vector<int> card(card_num);
    for (int i = 0; i < card_num; i++) cin >> card[i];
    sort(card.begin(), card.end());
    card.erase(unique(card.begin(), card.end()), card.end());

    int largest = card.back();
    vector<int> next_largest(largest + 1, -1);
    for (int i = 0; i < (int)card.size(); i++) next_largest[card[i]] = i;
    for (int i = largest - 1; i >= 0; i--) if (next_largest[i] == -1) next_largest[i] = next_largest[i + 1];

    vector<vector<pair<int, int>>> good_links(largest + 1);
    for (int i = 0; i < (int)card.size() - 1; i++){
        good_links[card[i + 1] % card[i]].push_back({i, i + 1});
        for (int at = 2 * card[i]; at <= largest; at += card[i]){
            int good_mod = next_largest[at];
            good_links[card[good_mod] % card[i]].push_back({i, good_mod});
        }
    }

    long long ans = 0;
    DisjointSet dsu((int)card.size());
    for (int cost = 0; cost <= largest; cost++){
        for (const pair<int, int> &link : good_links[cost]){
            if (dsu.unite(link)){
                ans += cost;
            }
        }
    }

    cout << ans;
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14