제출 #195585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
195585		dolphingarlic	Sirni (COCI17_sirni)	C++14	98 / 140	5091 ms	377128 KiB

sirni

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

int a[100001];
pair<int, pair<int, int>> edges[100000001];

int cmp[100001];
int find(int A) {
	while (A != cmp[A]) cmp[A] = cmp[cmp[A]], A = cmp[A];
	return A;
}
void onion(int A, int B) {
	cmp[find(A)] = cmp[find(B)];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	set<int> s;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		s.insert(x);
	}
	n = 0;
	for (int i : s) a[n++] = i;

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (i != n - 1) edges[cnt++] = {a[i + 1] % a[i], {i, i + 1}};
		int lb = i + 1;
		for (int j = 2 * a[i]; j <= a[n - 1]; j += a[i]) {
			while (a[lb] < j) lb++;
			pair<int, pair<int, int>> nxt = {a[lb] % a[i], {i, lb}};
			if (edges[cnt - 1] != nxt) edges[cnt++] = nxt;
		}
	}
	
	sort(edges, edges + cnt);
	for (int i = 0; i < n; i++) cmp[i] = i;
	long long ans = 0;
	for (int i = 0; i < cnt; i++) {
		pair<int, int> verts = edges[i].second;
		if (find(verts.first) != find(verts.second)) {
			ans += edges[i].first;
			onion(verts.first, verts.second);
		}
	}
	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: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14