oj.uz

Submission #195587

# Submission time Handle Problem Language Result Execution time Memory
195587 2020-01-16T13:27:34 Z dolphingarlic Sirni (COCI17_sirni) C++14
140 / 140
 4409 ms 711108 KB 
#include <bits/stdc++.h>
using namespace std;

int a[100001];
vector<pair<int, int>> edges[10000001];

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 235512 KB Output is correct
2 Correct 367 ms 264676 KB Output is correct
3 Correct 253 ms 235612 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 235368 KB Output is correct
2 Correct 1893 ms 630508 KB Output is correct
3 Correct 258 ms 236024 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 235440 KB Output is correct
2 Correct 253 ms 235408 KB Output is correct
3 Correct 254 ms 235384 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1676 ms 250200 KB Output is correct
2 Correct 1666 ms 277980 KB Output is correct
3 Correct 1264 ms 259792 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 237900 KB Output is correct
2 Correct 391 ms 258424 KB Output is correct
3 Correct 1241 ms 249236 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1775 ms 261856 KB Output is correct
2 Correct 1922 ms 296532 KB Output is correct
3 Correct 1669 ms 258908 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 240672 KB Output is correct
2 Correct 1755 ms 295504 KB Output is correct
3 Correct 1405 ms 260096 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1843 ms 253396 KB Output is correct
2 Correct 3547 ms 598812 KB Output is correct
3 Correct 1856 ms 256760 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1842 ms 257852 KB Output is correct
2 Correct 4409 ms 711108 KB Output is correct
3 Correct 2027 ms 313880 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 238540 KB Output is correct
2 Correct 3895 ms 598128 KB Output is correct
3 Correct 1466 ms 262964 KB Output is correct