oj.uz

Submission #949298

# Submission time Handle Problem Language Result Execution time Memory
949298 2024-03-19T05:20:37 Z Baytoro Sirni (COCI17_sirni) C++17
98 / 140
 1694 ms 786432 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;
ll nxt[N],par[N];
vector< pair<int,int> > g[N];
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(rand()%2) swap(a,b);
	par[a]=b;
	return 1;
}
void solve(){
	int n;cin>>n;
	vector<ll> p(n);
	for(int i=0;i<n;i++) cin>>p[i];
	sort(all(p));
	ll mx=0;
	for(int i=0;i<n;i++){
		nxt[p[i]]=p[i];
		mx=max(mx,p[i]);
		par[p[i]]=p[i];
	}
	for(int i=mx;i>=0;i--){
		if(nxt[i]==0) nxt[i]=nxt[i+1];
	}
	vector<pair<int,pair<int,int> > > a;
	for(int i=0;i<n;i++){
		if(i<n-1 && p[i]==p[i+1]) continue;
		g[p[i+1]%p[i]].pb(make_pair(p[i+1],p[i]));
		//a.pb(mp(p[i+1]%p[i],mp(p[i],p[i+1])));
		for(int j=p[i]*2;j<=mx;j+=p[i]){
			//a.pb(mp(nxt[j]%p[i],mp(p[i],nxt[j])));
			g[nxt[j]%p[i]].pb(make_pair(nxt[j],p[i]));
		}
	}
	sort(all(a));
	ll ans=0;
	for(int i=0;i<=mx;i++){
		for(auto it: g[i])
			if(add(it.fr,it.sc)) ans+=i;
	}
	cout<<ans<<endl;
}
int main(){
	solve();
}

Subtask #1
0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 235348 KB Output is correct
2 Correct 1196 ms 708772 KB Output is correct
3 Correct 149 ms 318388 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 317572 KB Output is correct
2 Incorrect 140 ms 316240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 261260 KB Output is correct
2 Correct 194 ms 289524 KB Output is correct
3 Correct 158 ms 272312 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 252756 KB Output is correct
2 Correct 162 ms 270672 KB Output is correct
3 Correct 115 ms 253460 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 273376 KB Output is correct
2 Correct 221 ms 307048 KB Output is correct
3 Correct 138 ms 270456 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 241976 KB Output is correct
2 Correct 222 ms 307820 KB Output is correct
3 Correct 152 ms 272168 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 405076 KB Output is correct
2 Correct 1433 ms 750648 KB Output is correct
3 Correct 286 ms 408356 KB Output is correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 409324 KB Output is correct
2 Runtime error 1297 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 365900 KB Output is correct
2 Correct 1694 ms 717148 KB Output is correct
3 Correct 143 ms 274872 KB Output is correct