Submission #1301964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301964		EkinOnal	Sirni (COCI17_sirni)	C++20	70 / 140	5103 ms	851968 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 = 1e18;
const int mod = 2019201997;
#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(MAX),sz(MAX);

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;
}	
vector<array<int,3>> edges;
void solve(){
	int n; cin>>n;
	vi val(1e7+2);	set<pii> st;
	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());

	for(int i=0;i<v.size();i++){
		// cout<<v[i]<<"  23\n";
		val[v[i]]=i+1,st.insert({v[i],i+1});
	}
	
	// cout<<val[2]<<"  37\n";

	for(int i=1;i<=1e7;i++){
		if(!val[i]) continue;
		for(int j=i;j<=1e7;j+=i){
			
			auto itr = st.lower_bound({j+(j==i),-1});
			if(itr==st.end() || (*itr).f>=j+i ) continue;

			edges.pb({ (*itr).f % i , val[i] , (*itr).s } );
		}
	}
	sort(edges.begin(),edges.end());

	int ans=0;
	for(auto u : edges){
		if(find(u[1])==find(u[2])) continue;
		ans+=u[0]; unite(u[1],u[2]);
	}
	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: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14