Submission #1271691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271691		firegirlwaterboy	Sirni (COCI17_sirni)	C++20	14 / 140	243 ms	302604 KiB

sirni

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

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

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

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

    bool unite(int n1, int n2) {
        n1 = find(n1);
        n2 = find(n2);
        if (n1 == n2) {
            return false;
        }
        if (sizes[n1] < sizes[n2]) {
            swap(n1, n2);
        }
        sizes[n1] += sizes[n2];
        parents[n2] = n1;
        return true;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> cards(n);
    for (int &c : cards) {
        cin >> c;
    }
    sort(cards.begin(), cards.end());
    cards.erase(unique(cards.begin(), cards.end()), cards.end());
    int mx = cards.back();
    vector<int> nxt(mx + 1, -1);
    for (int i = 0; i < n; i++) {
        nxt[cards[i]] = i;
    }
    for (int c = mx - 1; c >= 0; c--) {
        if (nxt[c] == -1) nxt[c] = nxt[c + 1];
    }
    vector<vector<pii>> good_links(mx + 1);
    for (int i = 0; i < n - 1; i++) {
        good_links[cards[i + 1] % cards[i]].push_back({i, i + 1});
        for (int at = 2 * cards[i]; at <= mx; at += cards[i]) {
            int good_mod = nxt[at];
            good_links[cards[good_mod] % cards[i]].push_back({i, good_mod});
        }
    }
    ll ans = 0;
    DisjointSets dsu(n);
    for (int c = 0; c <= mx; c++) {
        for (pii link : good_links[c]) {
            bool tmp = dsu.unite(link.first, link.second);
            ans += c * tmp;
        }
    }
    cout << ans << "\n";
}

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