oj.uz

Submission #195583

# Submission time Handle Problem Language Result Execution time Memory
195583 2020-01-16T13:17:12 Z dolphingarlic Sirni (COCI17_sirni) C++14
70 / 140
 5000 ms 315560 KB 
#include <bits/stdc++.h>
using namespace std;

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

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;

	for (int i = 0; i < n; i++) {
		if (i != n - 1) edges.insert({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++;
			edges.insert({a[lb] % a[i], {i, lb}});
		}
	}
	
	for (int i = 0; i < n; i++) cmp[i] = i;
	long long ans = 0;
	for (pair<int, pair<int, int>> e : edges) {
		if (find(e.second.first) != find(e.second.second)) {
			ans += e.first;
			onion(e.second.first, e.second.second);
		}
	}
	cout << ans;
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 403 ms 12296 KB Output is correct
3 Correct 8 ms 1244 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 2562 ms 4500 KB Output is correct
3 Correct 10 ms 1016 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 7 ms 936 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2671 ms 69032 KB Output is correct
2 Correct 4842 ms 247136 KB Output is correct
3 Correct 2509 ms 96500 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 9976 KB Output is correct
2 Correct 3568 ms 133364 KB Output is correct
3 Correct 2009 ms 70032 KB Output is correct

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3811 ms 149668 KB Output is correct
2 Execution timed out 5077 ms 315560 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 24312 KB Output is correct
2 Execution timed out 5107 ms 281744 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3564 ms 81504 KB Output is correct
2 Execution timed out 5030 ms 285528 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3758 ms 80672 KB Output is correct
2 Execution timed out 5089 ms 225456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 12920 KB Output is correct
2 Execution timed out 5068 ms 232528 KB Time limit exceeded
3 Halted 0 ms 0 KB -