oj.uz

답안 #484525

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
484525 2021-11-04T02:01:16 Z SansPapyrus683 Sirni (COCI17_sirni) C++17
84 / 140
 1055 ms 786436 KB 
#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>

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

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 get_ultimate(int n) {
            return parents[n] == n ? n : (parents[n] = get_ultimate(parents[n]));
        }

        bool link(int n1, int n2) {
            n1 = get_ultimate(n1);
            n2 = get_ultimate(n2);
            if (n1 == n2) {
                return false;
            }
            if (sizes[n1] < sizes[n2]) {
                std::swap(n1, n2);
            }
            sizes[n1] += sizes[n2];
            parents[n2] = n1;
            return true;
        }
};

/**
 * https://oj.uz/problem/view/COCI17_sirni
 * 4
 * 2
 * 6
 * 3
 * 11 should output 1
 */
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; 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<pair<int, pair<int, int>>> good_links;
    for (int i = 0; i < cards.size() - 1; i++) {
        good_links.push_back({cards[i + 1] % cards[i], {i, i + 1}});
        for (int at = 2 * cards[i]; at <= largest; at += cards[i]) {
            int good_mod = next_largest[at];
            good_links.push_back({cards[good_mod] % cards[i], {i, good_mod}});
        }
    }

    std::sort(good_links.begin(), good_links.end());
    long long total_cost = 0;
    DisjointSets linked_cards(cards.size());
    for (const auto& [cost, to_link] : good_links) {
        total_cost += cost * linked_cards.link(to_link.first, to_link.second);
    }
    cout << total_cost << endl;
}

Compilation message

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

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 39532 KB Output is correct
2 Correct 288 ms 88596 KB Output is correct
3 Correct 42 ms 39716 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 460 KB Output is correct
2 Runtime error 815 ms 786436 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 39564 KB Output is correct
2 Correct 43 ms 39376 KB Output is correct
3 Correct 43 ms 39660 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 29404 KB Output is correct
2 Correct 703 ms 54448 KB Output is correct
3 Correct 338 ms 54012 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 7428 KB Output is correct
2 Correct 372 ms 54016 KB Output is correct
3 Correct 188 ms 27432 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 399 ms 54036 KB Output is correct
2 Correct 936 ms 103296 KB Output is correct
3 Correct 288 ms 29356 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 7544 KB Output is correct
2 Correct 942 ms 103240 KB Output is correct
3 Correct 319 ms 29404 KB Output is correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 64580 KB Output is correct
2 Runtime error 905 ms 786436 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 334 ms 64524 KB Output is correct
2 Runtime error 939 ms 786436 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 42700 KB Output is correct
2 Runtime error 1055 ms 786436 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -