oj.uz

Submission #679633

# Submission time Handle Problem Language Result Execution time Memory
679633 2023-01-08T17:30:03 Z as111 Sirni (COCI17_sirni) C++17
140 / 140
 3029 ms 711956 KB 
#include <bits/stdc++.h>

#define MAXN 100000
using namespace std;
typedef pair<int, int> pi;
const int MAXP = 1e7;

int N;
set<int> cards;
vector<pi> edges[MAXP + 5]; // PQ of edges
priority_queue<pair<int, pi>> PQ;

int parent[MAXN + 5]; // initialize parent[i] = i
int findRoot(int a) {
	return parent[a] = (parent[a] == a ? a : findRoot(parent[a]));
}
int join(int a, int b) {
	a = findRoot(a); b = findRoot(b);
	if (a == b) return 0;
	parent[a] = b;
	return 1;
}


int card[MAXN + 5]; // value for each card ID
map<int, int> ID; // card value to card ID
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int P;
		cin >> P;
		cards.insert(P);
	}
	N = 0;
	for (int c : cards) {
		card[N++] = c;
	}
	for (int i = 0; i < N;i++) {
		int s = i + 1;
		for (int j = card[i]; j < MAXP; j += card[i]) {
			while (s < N && card[s] < j) s++;
			if (s < N) edges[card[s] % card[i]].emplace_back(i, s);
		}
	}
	iota(parent, parent + N, 0);
	long long ans = 0;
	for (int p = 0; p < MAXP;p++) {
		for (auto curr : edges[p]) {
			int f = curr.first;
			int s = curr.second;
			if (join(f, s))ans += p;
		}
	}
	cout << ans<<endl;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 235316 KB Output is correct
2 Correct 204 ms 264496 KB Output is correct
3 Correct 136 ms 235512 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 235216 KB Output is correct
2 Correct 1258 ms 629960 KB Output is correct
3 Correct 126 ms 235976 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 235268 KB Output is correct
2 Correct 130 ms 235440 KB Output is correct
3 Correct 126 ms 235392 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1794 ms 249988 KB Output is correct
2 Correct 1742 ms 278092 KB Output is correct
3 Correct 1237 ms 260524 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 237900 KB Output is correct
2 Correct 278 ms 258732 KB Output is correct
3 Correct 1336 ms 249640 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1764 ms 261668 KB Output is correct
2 Correct 1930 ms 295992 KB Output is correct
3 Correct 1701 ms 259212 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 240428 KB Output is correct
2 Correct 1332 ms 295460 KB Output is correct
3 Correct 1395 ms 260676 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1337 ms 253464 KB Output is correct
2 Correct 2419 ms 599740 KB Output is correct
3 Correct 1298 ms 257012 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1324 ms 257500 KB Output is correct
2 Correct 3029 ms 711956 KB Output is correct
3 Correct 1424 ms 313760 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 238404 KB Output is correct
2 Correct 2594 ms 598700 KB Output is correct
3 Correct 1472 ms 263156 KB Output is correct