oj.uz

답안 #949306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
949306 2024-03-19T05:36:42 Z vjudge1 Sirni (COCI17_sirni) C++17
140 / 140
 1755 ms 747596 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 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);
	ll mx=0;
	for(int i=0;i<n;i++){
		cin>>p[i];
		mx=max(mx,p[i]);
	}
	sort(all(p));
	p.erase(unique(all(p)),p.end());
	n=p.size();
	vector<int> nxt(mx+1,-1);
	for(int i=0;i<n;i++){
		nxt[p[i]]=i;
		par[i]=i;
	}
	for(int i=mx-1;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+1]%p[i]].pb(make_pair(i+1,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[p[nxt[j]]%p[i]].pb(make_pair(nxt[j],i));
		}
	}
	sort(all(a));
	ll ans=0;
	for(int i=0;i<=mx;i++){
		for(auto it: g[i]){
			//cout<<it.fr<<' '<<it.sc<<' '<<f(it.fr)<<' '<<f(it.sc)<<' ';
			if(add(it.fr,it.sc)){
				ans+=i;
				//cout<<"<-";
			}
			//cout<<endl;
		}
	}
	cout<<ans<<endl;
}
int main(){
	solve();
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 274512 KB Output is correct
2 Correct 204 ms 303700 KB Output is correct
3 Correct 121 ms 274520 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 235348 KB Output is correct
2 Correct 1028 ms 669088 KB Output is correct
3 Correct 118 ms 275140 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 274556 KB Output is correct
2 Correct 112 ms 274260 KB Output is correct
3 Correct 121 ms 274516 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 250204 KB Output is correct
2 Correct 183 ms 278592 KB Output is correct
3 Correct 132 ms 261000 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 241248 KB Output is correct
2 Correct 136 ms 262744 KB Output is correct
3 Correct 110 ms 248296 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 262256 KB Output is correct
2 Correct 214 ms 296164 KB Output is correct
3 Correct 136 ms 259592 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 239772 KB Output is correct
2 Correct 199 ms 296728 KB Output is correct
3 Correct 136 ms 261044 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 204 ms 288848 KB Output is correct
2 Correct 1152 ms 634268 KB Output is correct
3 Correct 222 ms 291552 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 293096 KB Output is correct
2 Correct 1755 ms 747596 KB Output is correct
3 Correct 328 ms 348820 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 276816 KB Output is correct
2 Correct 1591 ms 635068 KB Output is correct
3 Correct 135 ms 263232 KB Output is correct