oj.uz

Submission #949295

# Submission time Handle Problem Language Result Execution time Memory
949295 2024-03-19T05:12:42 Z Baytoro Sirni (COCI17_sirni) C++17
0 / 140
 353 ms 131240 KB 
#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define mp make_pair
#define ll long long
const ll INF=1e18,N=1e7+5,M=1e6+1;
ll nxt[N],par[M],sz[M];
int f(ll x){
	if(par[x]==x) return x;
	return par[x]=f(par[x]);
}
bool add(ll a, ll b){
	a=f(a),b=f(b);
	if(a==b) return 0;
	if(sz[a]>sz[b]) swap(a,b);
	par[a]=b;
	sz[b]+=sz[a];
	return 1;
}
void solve(){
	int n;cin>>n;
	vector<ll> p(n);
	ll mx=0;
	for(int i=0;i<n;i++){
		cin>>p[i];
		mx=max(mx,p[i]);
	}
	sort(all(p));
	for(int i=0;i<=mx;i++) nxt[i]=-1;
	for(int i=0;i<n;i++){
		nxt[p[i]]=i;
		par[i]=i;
		sz[i]=1;
	}
	
	for(int i=mx;i>=0;i--){
		if(nxt[i]==-1) nxt[i]=nxt[i+1];
	}
	vector<pair<int,pair<int,int> > > a;
	for(int i=0;i<n-1;i++){
		if(i<n-1 && p[i]==p[i+1]) continue;
		//g[p[i]].pb(make_pair(p[i+1],p[i+1]%p[i]));
		a.pb(mp(p[i+1]%p[i],mp(i,i+1)));
		for(int j=p[i]*2;j<=mx;j+=p[i]){
			a.pb(mp(p[nxt[j]]%p[i],mp(i,nxt[j])));
			//g[p[i]].pb(make_pair(nxt[j],nxt[j]%p[i]));
		}
	}
	//for(int i=1;i<=mx;i++) cout<<nxt[i]<<' ';
	//cout<<endl;
	sort(all(a));
	ll ans=0;
	for(auto it: a){
		//cerr<<it.sc.fr<<' '<<it.sc.sc<<' '<<it.fr<<' ';
		if(add(it.sc.fr,it.sc.sc)){
			//cerr<<"<-";
			ans+=it.fr;
		}
		//cerr<<endl;
	}
	cout<<ans<<endl;
}
int main(){
	solve();
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 81756 KB Output is correct
2 Incorrect 270 ms 131240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 82252 KB Output is correct
2 Incorrect 32 ms 81740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 175 ms 44212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 16844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 353 ms 67756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 15564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 253 ms 112576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 287 ms 112820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 86524 KB Output isn't correct
2 Halted 0 ms 0 KB -