Submission #671526

#	Time	Username	Problem	Language	Result	Execution time	Memory
671526		Koful123	Sirni (COCI17_sirni)	C++17	140 / 140	3038 ms	552124 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const int N = 1e7 + 5;
int exist[N],con[N],par[N],sz[N];

struct node{
	int a,b,c;
	bool operator < (const node other) const{
		return c < other.c;
	};
};

struct DSU{
	int find(int x){
		if(x == par[x]) return x;
		return par[x] = find(par[x]);
	}
	void unite(int a,int b){
		a = find(a),b = find(b);
		if(sz[a] < sz[b]) swap(a,b);
		sz[a] += sz[b];
		par[b] = a;
		sz[b] = 0;
	}
};

void solve(){

	int n;
	cin >> n;

	vector<int> v(n);
	for(int i = 0; i < n; i++){
		cin >> v[i];
	}

	sort(all(v)); v.resize(unique(all(v)) - v.begin());
	for(int x : v){
		exist[x] = 1;
	}

	DSU dsu;
	for(int i = N - 2; i >= 1; i--){
		con[i] = (exist[i] ? i : con[i + 1]);
		par[i] = i,sz[i] = 1;
	}

	vector<node> edges;
	for(int x : v){
		edges.pb({x,con[x+1],con[x+1] % x});
		for(int j = x*2; j < N; j += x){
			if(!con[j] || con[j] >= j + x) continue;
			edges.pb({x,con[j],con[j] % x});
		}
	}

	sort(all(edges)); long long ans = 0;
	for(auto[a,b,c] : edges){
		if(dsu.find(a) != dsu.find(b)){
			dsu.unite(a,b), ans +=  c;
		}
	}

	cout << ans << endl;
}
 
signed main(){
 	
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int t = 1;
//	cin >> t;
 
	while(t--)
		solve();
 	
	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