Submission #1175207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175207		nuutsnoynton	Sirni (COCI17_sirni)	C++20	126 / 140	2885 ms	786956 KiB

sirni

#include<bits/stdc++.h>

using namespace std;
using ll = int;
const ll N = 1e7 + 2;
ll a[100005];
vector < pair < ll, ll > > v[N];
ll ataman[100005];
ll Get(ll x) {
	if (x == ataman[x]) return x;
	return ataman[x] = Get(ataman[x]);
}

void Unite(ll x, ll y) {
	x = Get(x);
	y = Get(y);
	if ( x == y) return ;
	if ( x > y) swap(x, y);
	ataman[y] = x;
}

int main() {
	ll n, m, r, x, y, i, j, ans, t;

	cin >> n;
	
	set < ll > S;
	
	for (i = 1; i <= n; i ++) {
		cin >> x;
		S.insert(x);
	} 
	n = S.size(); 
	
	r = 1;
	for (ll X : S) {
		a[r] = X;
		r ++;
	}

	for (i = 1; i <= n; i ++) {
		for ( j = 2 * a[i]; j <= a[n]; j += a[i]) {
			r = lower_bound(a + 1, a + n + 1, j) - a;
			if ( r> n) break;
			v[a[r] - j].push_back(make_pair(i, r));
		}
	}
	
	
	for (i = 1; i < n; i ++) {
		v[a[i + 1] % a[i]].push_back(make_pair(i, i + 1));
	}
	
	for (i = 1; i <= n; i ++) ataman[i] = i;
	ans = 0;
	
	for (i = 0; i <= 1e7; i ++) {
		for ( pair < ll, ll >P : v[i]) {
			x = P.first;
			y = P.second;
			x = Get(x);
			y = Get(y);
			if ( x != y) {
				Unite(x, y);
				ans += i;
			}
		}
	}
	
	cout << ans << endl;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 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