oj.uz

Submission #483160

# Submission time Handle Problem Language Result Execution time Memory
483160 2021-10-28T02:03:15 Z KazamaHoang Sirni (COCI17_sirni) C++14
140 / 140
 2159 ms 98016 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 8560 KB Output is correct
2 Correct 495 ms 4300 KB Output is correct
3 Correct 293 ms 8516 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 488 KB Output is correct
2 Correct 124 ms 1224 KB Output is correct
3 Correct 50 ms 8248 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 8956 KB Output is correct
2 Correct 101 ms 6268 KB Output is correct
3 Correct 270 ms 8640 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 12496 KB Output is correct
2 Correct 670 ms 11060 KB Output is correct
3 Correct 121 ms 10308 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 10332 KB Output is correct
2 Correct 1287 ms 7356 KB Output is correct
3 Correct 448 ms 6192 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 11884 KB Output is correct
2 Correct 369 ms 9664 KB Output is correct
3 Correct 118 ms 10396 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 2884 KB Output is correct
2 Correct 532 ms 9540 KB Output is correct
3 Correct 115 ms 9836 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 98016 KB Output is correct
2 Correct 483 ms 80148 KB Output is correct
3 Correct 699 ms 95548 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 93324 KB Output is correct
2 Correct 1160 ms 77912 KB Output is correct
3 Correct 105 ms 80708 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 77172 KB Output is correct
2 Correct 2159 ms 64176 KB Output is correct
3 Correct 128 ms 10436 KB Output is correct