Submission #1114487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114487		ssitaram	Sirni (COCI17_sirni)	C++17	140 / 140	1425 ms	747028 KiB

sirni

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14