oj.uz

Submission #671526

# Submission time Handle Problem Language Result Execution time Memory
671526 2022-12-13T06:20:20 Z Koful123 Sirni (COCI17_sirni) C++17
140 / 140
 3038 ms 552124 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 121500 KB Output is correct
2 Correct 110 ms 122808 KB Output is correct
3 Correct 70 ms 121868 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 117964 KB Output is correct
2 Correct 287 ms 119212 KB Output is correct
3 Correct 72 ms 121864 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 121800 KB Output is correct
2 Correct 71 ms 120240 KB Output is correct
3 Correct 71 ms 121828 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 134540 KB Output is correct
2 Correct 615 ms 171508 KB Output is correct
3 Correct 281 ms 146892 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 124940 KB Output is correct
2 Correct 461 ms 170812 KB Output is correct
3 Correct 287 ms 132648 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 171424 KB Output is correct
2 Correct 751 ms 220984 KB Output is correct
3 Correct 268 ms 146988 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 125060 KB Output is correct
2 Correct 814 ms 220752 KB Output is correct
3 Correct 258 ms 146936 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 182036 KB Output is correct
2 Correct 2051 ms 552124 KB Output is correct
3 Correct 230 ms 182796 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 182072 KB Output is correct
2 Correct 2899 ms 551068 KB Output is correct
3 Correct 272 ms 182780 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 155084 KB Output is correct
2 Correct 3038 ms 544088 KB Output is correct
3 Correct 296 ms 147444 KB Output is correct