Submission #468706

#	Time	Username	Problem	Language	Result	Execution time	Memory
468706		Autron	Sirni (COCI17_sirni)	C++14	140 / 140	3863 ms	708308 KiB

sirni

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

int n;
vector<int> p;
vector<pair<int, int>> e[10000002];
vector<int> fat, sz;

int get(int x){
	if(fat[x]==x) return x;
	return fat[x]=get(fat[x]);
}

int sol=0;
void join(int a, int b, int c){
	a=get(a), b=get(b);
	if(a==b) return;
	sol+=c;
	if(sz[a]<sz[b]) swap(a, b);
	sz[a]+=sz[b];
	fat[b]=a;
}

int main(){
	cin>>n;
	p.resize(n+1), fat.resize(n+1), sz.resize(n+1);
	for(int i=1;i<=n;++i) cin>>p[i], fat[i]=i, sz[i]=1;
	sort(p.begin()+1, p.end());
	p.resize(unique(p.begin(), p.end())-p.begin());
	n=p.size()-1;
	int m=p[n];
	for(int i=1;i<=n;++i){
		int j=i+1;
		for(int x=p[i];x<=m;x+=p[i]){
			while(j<=n&&p[j]<x) j++;
			if(j<=n) e[p[j]%p[i]].push_back({i, j});
		}
	}
	for(int i=0;i<=m;++i){
		for(auto it:e[i]) join(it.first, it.second, i);
	}
	cout<<sol<<"\n";
	return 0;
}

• 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