oj.uz

Submission #882883

# Submission time Handle Problem Language Result Execution time Memory
882883 2023-12-04T03:09:00 Z SansPapyrus683 Sirni (COCI17_sirni) C++17
140 / 140
 1497 ms 763044 KB 
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::pair;
using std::vector;

// BeginCodeSnip{DSU (from module)}
struct DSU {
    vector<int> e;
    DSU(int N) { e = vector<int>(N, -1); }

    // get representive component (uses path compression)
    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

    bool same_set(int a, int b) { return get(a) == get(b); }

    int size(int x) { return -e[get(x)]; }

    bool unite(int x, int y) {  // union by size
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) std::swap(x, y);
        e[x] += e[y];
        e[y] = x;
        return true;
    }
};
// EndCodeSnip

int main() {
    int card_num;
    std::cin >> card_num;
    vector<int> cards(card_num);
    for (int& c : cards) {
        std::cin >> c;
        assert(c >= 1);
    }
    std::sort(cards.begin(), cards.end());
    // we can erase the dupes bc modding them with the original one = 0
    cards.erase(std::unique(cards.begin(), cards.end()), cards.end());

    int largest = *std::max_element(cards.begin(), cards.end());
    vector<int> next_largest(largest + 1, -1);
    for (int i = 0; i < cards.size(); i++) {
        next_largest[cards[i]] = i;
    }
    for (int c = largest - 1; c >= 0; c--) {
        // if this isn't assigned yet, assign it the previous one
        if (next_largest[c] == -1) {
            next_largest[c] = next_largest[c + 1];
        }
    }

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

    long long total_cost = 0;
    DSU linked_cards(cards.size());
    for (int c = 0; c <= largest; c++) {
        for (const pair<int, int>& link : good_links[c]) {
            bool result = linked_cards.unite(link.first, link.second);
            total_cost += c * result;
        }
    }

    cout << total_cost << endl;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < cards.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
sirni.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < cards.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 274308 KB Output is correct
2 Correct 168 ms 302688 KB Output is correct
3 Correct 102 ms 273492 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 924 ms 681272 KB Output is correct
3 Correct 100 ms 275056 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 274452 KB Output is correct
2 Correct 95 ms 273756 KB Output is correct
3 Correct 99 ms 274516 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 38620 KB Output is correct
2 Correct 106 ms 68492 KB Output is correct
3 Correct 77 ms 50808 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29788 KB Output is correct
2 Correct 83 ms 51408 KB Output is correct
3 Correct 50 ms 25756 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 50548 KB Output is correct
2 Correct 139 ms 91216 KB Output is correct
3 Correct 69 ms 47532 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 9660 KB Output is correct
2 Correct 136 ms 86944 KB Output is correct
3 Correct 71 ms 50500 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 288812 KB Output is correct
2 Correct 950 ms 660860 KB Output is correct
3 Correct 180 ms 291304 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 292844 KB Output is correct
2 Correct 1497 ms 763044 KB Output is correct
3 Correct 288 ms 351056 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 276948 KB Output is correct
2 Correct 1483 ms 635732 KB Output is correct
3 Correct 78 ms 54416 KB Output is correct