oj.uz

답안 #1060464

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1060464 2024-08-15T15:26:29 Z khanhtb Sirni (COCI17_sirni) C++14
140 / 140
 1122 ms 747008 KB 
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

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

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]) { std::swap(n1, n2); }
		sizes[n1] += sizes[n2];
		parents[n2] = n1;
		return true;
	}
};

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 = cards.back();  // since we sorted the cards already
	// next_largest[i] contains the index of lowest card value that's >= i
	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++) {
		// get all relevant cards this card could be connected to
		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;
	DisjointSets 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:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 0; i < cards.size(); i++) { next_largest[cards[i]] = i; }
      |                  ~~^~~~~~~~~~~~~~
sirni.cpp:59:20: 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

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 274152 KB Output is correct
2 Correct 175 ms 302672 KB Output is correct
3 Correct 129 ms 273492 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 753 ms 668472 KB Output is correct
3 Correct 128 ms 275024 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 274536 KB Output is correct
2 Correct 118 ms 273744 KB Output is correct
3 Correct 121 ms 274512 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 38280 KB Output is correct
2 Correct 100 ms 66436 KB Output is correct
3 Correct 67 ms 48808 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 29784 KB Output is correct
2 Correct 64 ms 51000 KB Output is correct
3 Correct 47 ms 24624 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 49688 KB Output is correct
2 Correct 119 ms 83412 KB Output is correct
3 Correct 64 ms 46764 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 9660 KB Output is correct
2 Correct 128 ms 84116 KB Output is correct
3 Correct 74 ms 48564 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 288336 KB Output is correct
2 Correct 809 ms 633160 KB Output is correct
3 Correct 187 ms 291872 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 292384 KB Output is correct
2 Correct 1122 ms 747008 KB Output is correct
3 Correct 280 ms 348532 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 276820 KB Output is correct
2 Correct 973 ms 634972 KB Output is correct
3 Correct 68 ms 51132 KB Output is correct