Submission #1191421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191421		hikari1234	Sirni (COCI17_sirni)	C++20	140 / 140	1038 ms	751164 KiB

sirni

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ff first
#define ss second
int n;
int a[100005];
set<int> s;
vector<int> cards;
int par[100005], sz[100005];
int fin(int x){
	if(par[x]==x) return x;
	return par[x]=fin(par[x]); 	
}
bool unite(int x, int y){
	x=fin(x), y=fin(y);
	if(x==y) return 0;
	if(sz[y]>sz[x]) swap(x,y);
	sz[x]+=sz[y];
	par[y]=x;
	return 1;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    sz[0]=1;
    for(int i=1; i<=n; i++){
    	cin>>a[i];
    	s.insert(a[i]);
    	sz[i]=1;
    	par[i]=i;
	}
	for(auto &x: s){
		cards.push_back(x);	
	}
	int lim=cards.back();
	vector<pair<int,int>> edges[lim+5];
	int comp=cards.size();
	int idx[lim+5];
	memset(idx,-1,sizeof(idx));
	for(int i=0; i<cards.size(); i++){
		idx[cards[i]]=i;
	}
	for(int i=lim; i>=0; i--){
		if(idx[i]==-1){
			idx[i]=idx[i+1];
		}
	}
	for(int i=0; i<cards.size()-1; i++){
		edges[cards[i+1]%cards[i]].emplace_back(i,i+1);
		for(int j=cards[i]*2; j<=lim; j+=cards[i]){
			edges[cards[idx[j]]%cards[i]].emplace_back(i,idx[j]);
		}
	}
	long long tot=0;
	for(int i=0; i<=lim; i++){
		for(pair<int,int> &j: edges[i]){
			if(unite(j.ff,j.ss)){
//				cout<<i<<" "<<j.ff<<" "<<j.ss<<endl;
				tot+=i;
				comp--;
				if(comp==1){
					cout<<tot<<endl;
					return 0;
				}
			}
		}
	}
	cout<<tot<<endl;
}

• 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