제출 #1301989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1301989		EkinOnal	Sirni (COCI17_sirni)	C++20	140 / 140	1265 ms	746960 KiB

sirni

#include <bits/stdc++.h>
using namespace std;

// #define double long double
// #define int long long
#define pb push_back
#define vi vector<int>
#define vpii vector<pair<int,int>>
#define MAX 200005
#define f first
#define s second
const int INF = 1e9;
const int mod = 1e9+7;
#define pii pair<int,int>
	
int sum(int a,int b){return ((a%mod)+(b%mod))%mod;}
int mul(int a,int b){return ((a%mod)*(b%mod))%mod;}

vi dsu(1e5+2),sz(1e5+2);

int find(int a){
	if(dsu[a]==a) return a;
	return dsu[a]=find(dsu[a]);
}

void unite(int a,int b){
	a=find(a); b=find(b);
	if(a==b) return;
	if(sz[a]<sz[b]) swap(a,b);
	sz[a]+=sz[b]; dsu[b]=a;
}	

void solve(){
	int n; cin>>n;
	vi v(n); for(int i=0;i<n;i++) cin>>v[i],dsu[i]=i,sz[i]=1;

	sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
	n=v.size(); int largest=v.back();

	vi nxt(v[n-1]+2,-1); for(int i=0;i<n;i++) nxt[v[i]]=i;
	for(int i=v[n-1];i>0;i--){
		if(nxt[i]==-1) nxt[i]=nxt[i+1];
	}

	vector<vector<pair<int, int>>> edges(largest + 1);
	for(int i=0;i<n-1;i++){
		edges[v[i+1]%v[i]].pb({i, i+1 });
		for(int j=2*v[i];j<=v[n-1];j+=v[i]){

			// if(nxt[j]>=j+v[i]) continue;

			edges[v[nxt[j]] % v[i]].pb({ i , nxt[j] } );
		}
	}

	long long ans=0;
	for(int i=0;i<=largest;i++){
		for(auto u : edges[i]){
			if(find(u.f)==find(u.s)) continue;
			ans+=i; unite(u.f,u.s);
		}
	}
	cout<<ans<<endl;
}	
	
int32_t main(){
	// freopen("walk.in","r",stdin);
	// freopen("walk.out","w",stdout);

	int t=1; 
	// cin>>t;
	while(t--) solve();

}	

• 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