oj.uz

Submission #195581

# Submission time Handle Problem Language Result Execution time Memory
195581 2020-01-16T13:13:25 Z dolphingarlic Sirni (COCI17_sirni) C++14
84 / 140
 5000 ms 630920 KB 
#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() {
	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++;
			edges[cnt++] = {a[lb] - j, {i, lb}};
		}
	}
	
	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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 416 ms 33144 KB Output is correct
3 Correct 5 ms 632 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Execution timed out 5093 ms 552924 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 720 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 504 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1613 ms 18872 KB Output is correct
2 Correct 2055 ms 55120 KB Output is correct
3 Correct 1390 ms 31032 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 3360 KB Output is correct
2 Correct 459 ms 27764 KB Output is correct
3 Correct 1196 ms 17952 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1912 ms 33784 KB Output is correct
2 Correct 2556 ms 75128 KB Output is correct
3 Correct 1705 ms 29008 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 6868 KB Output is correct
2 Correct 2426 ms 76944 KB Output is correct
3 Correct 1484 ms 29580 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1804 ms 22520 KB Output is correct
2 Execution timed out 5098 ms 482296 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1895 ms 28424 KB Output is correct
2 Execution timed out 5078 ms 630920 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 3832 KB Output is correct
2 Execution timed out 5074 ms 471768 KB Time limit exceeded
3 Halted 0 ms 0 KB -