Submission #1175183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175183		Nomio	Sirni (COCI17_sirni)	C++20	140 / 140	3250 ms	750980 KiB

sirni

#include<bits/stdc++.h>
#define s second
#define f first
using namespace std;
using ll = long long;

const int maxn = 1e5 + 1;
const int MAXN = 1e7 + 1;

vector<int> pos(MAXN, -1);
int a[maxn], sz[maxn], p[maxn];
vector<pair<int, int>> edge[MAXN];

int find(int x) {
	if(a[x] == x) return x;
	return a[x] = find(a[x]);
}

int unite(int u, int v) {
	u = find(u);
	v = find(v);
	if(u == v) return -1;
	if(sz[u] > sz[v]) swap(u, v);
	sz[v] += sz[u];
	a[u] = v;
	return v;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	set<int> s;
	for(int i = 0; i < n; i++) {
		cin >> p[i];
		s.insert(p[i]);
	}
	vector<ll> v;
	for(int x : s) {
		v.push_back(x);
	}
	int N = v.size();
	for(int i = 0; i < N; i++) {
		a[i] = i;
		sz[i] = 1;
	}
	for(int i = 0; i < N; i++) {
		pos[v[i]] = i;
	}
	for(int i = 0; i < N - 1; i++){
		edge[v[i + 1] % v[i]].push_back({i, i +	1});
		for(ll j = v[i] * 2; j <= v[N - 1]; j += v[i]) {
			int x = *lower_bound(v.begin(), v.end(), j);
			edge[x % v[i]].push_back({i, pos[x]});
		}
	}
	ll ans = 0;
	for(int i = 0; i <= MAXN; i++) {
		for(pair<int, int> p : edge[i]) {
			int u = p.f;
			int v = p.s;
			if(find(u) != find(v)) {
				ans += i;
				int V = unite(u, v);
				if(sz[V] == N) {
					cout << ans << '\n';
					return 0;
				}
			}
		} 
	}
	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