oj.uz

Submission #1114487

# Submission time Handle Problem Language Result Execution time Memory
1114487 2024-11-19T04:55:08 Z ssitaram Sirni (COCI17_sirni) C++17
140 / 140
 1425 ms 747028 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct DSU {
	vector<int> p, sz;

	DSU(int n) : p(n), sz(n, 1) {
		iota(p.begin(), p.end(), 0);
	}

	int find(int i) {
		return p[i] = (p[i] == i ? i : find(p[i]));
	}

	bool uni(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return false;
		if (sz[a] < sz[b]) swap(a, b);
		sz[a] += sz[b];
		p[b] = a;
		return true;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	vector<int> p(n);
	for (int& i : p) cin >> i;
	sort(p.begin(), p.end());
	p.erase(unique(p.begin(), p.end()), p.end());
	n = p.size();
	int ma = p.back();
	vector<int> nxt(ma + 1);
	for (int i = n - 1; i >= 0; --i) {
		int o = (i == 0 ? -1 : p[i - 1]);
		for (int j = o + 1; j <= p[i]; ++j) {
			nxt[j] = i;
		}
	}
	vector<vector<pair<int, int>>> edges(ma + 1);
	for (int i = 0; i < n - 1; ++i) {
		edges[p[i + 1] % p[i]].push_back({i, i + 1});
		for (int j = 2 * p[i]; j <= ma; j += p[i]) {
			edges[p[nxt[j]] % p[i]].push_back({i, nxt[j]});
		}
	}
	DSU dsu(n);
	ll ans = 0;
	for (int i = 0; i <= ma; ++i) {
		for (pair<int, int> edge : edges[i]) {
			if (dsu.uni(edge.first, edge.second)) {
				ans += i;
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 274248 KB Output is correct
2 Correct 165 ms 302608 KB Output is correct
3 Correct 107 ms 273668 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 612 KB Output is correct
2 Correct 876 ms 668592 KB Output is correct
3 Correct 97 ms 275016 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 274404 KB Output is correct
2 Correct 98 ms 273884 KB Output is correct
3 Correct 108 ms 274348 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 39156 KB Output is correct
2 Correct 107 ms 73976 KB Output is correct
3 Correct 60 ms 51252 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29776 KB Output is correct
2 Correct 77 ms 51408 KB Output is correct
3 Correct 40 ms 25972 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 54732 KB Output is correct
2 Correct 137 ms 91084 KB Output is correct
3 Correct 60 ms 49316 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9924 KB Output is correct
2 Correct 141 ms 87472 KB Output is correct
3 Correct 62 ms 50740 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 289352 KB Output is correct
2 Correct 969 ms 633204 KB Output is correct
3 Correct 177 ms 291732 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 293336 KB Output is correct
2 Correct 1425 ms 747028 KB Output is correct
3 Correct 306 ms 348516 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 276992 KB Output is correct
2 Correct 1223 ms 636924 KB Output is correct
3 Correct 65 ms 54464 KB Output is correct