Submission #483160

#	Time	Username	Problem	Language	Result	Execution time	Memory
483160		KazamaHoang	Sirni (COCI17_sirni)	C++14	140 / 140	2159 ms	98016 KiB

sirni

#include <bits/stdc++.h>
#define INF 1000000000
#define M 1000000007
#define ll long long
#define MAX 10000001
using namespace std;

int a[MAX],m[MAX];
int par[MAX],r[MAX];

int getroot(int x){
	if (par[x]==x) return x;
	else return getroot(par[x]);
}

int union_(int x,int y){
	int rx = getroot(x);
	int ry = getroot(y);
	if (rx==ry) return 0;
	if (r[rx]>r[ry]){
		par[ry] = rx;
		r[rx]++;
	}
	else{
		par[rx] = ry;
		r[ry]++;
	}
	return 0;
}

int main(){
	int n;
	cin >> n;
	for (int i=0;i<n;i++){
		int x;scanf("%d",&x);
		m[x] = 1;
	}
	n = 0;
	for (int i=1;i<MAX;i++){
		if (m[i]){
			a[n++] = i;
			par[i] = i;
		}
	}
	int groups = n;
	int md = 0;
	ll sum = 0;
	while(groups!=1){
		for (int i=0;i<n;i++){
			for (int j=a[i]+md;j<MAX;j+=a[i]){
				if (m[j] && getroot(a[i])!=getroot(j)){
					union_(j,a[i]);
					sum+=md;
					groups--;
				}
			}
		}
		md++;
	}
	cout << sum << endl;
	return 0;
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   int x;scanf("%d",&x);
      |         ~~~~~^~~~~~~~~

• 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