oj.uz

Submission #989542

# Submission time Handle Problem Language Result Execution time Memory
989542 2024-05-28T09:43:01 Z re4ler Sirni (COCI17_sirni) C++17
140 / 140
 2266 ms 476300 KB 
#include<bits/stdc++.h>
using namespace std;
#define faster ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define getbit(x , i) ((x >> i) & 1)
typedef pair<int , int> pii;

const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
const int N = 1e7 + 5;

int n;
int a[maxn] , cha[maxn];
bool dd[N];

struct edge{
	int u , v , w;
};
edge e[50000005];

bool operator <(const edge &x , const edge &y){
	return x.w < y.w;	
}

int find(int u){
	if(cha[u] != u) cha[u] = find(cha[u]);
	return cha[u];	
}

void join(int u , int v){
	cha[u] = v;	
}

main()
{
    faster
    cin >> n;
    vector<int> b;
    b.pb(0);
    for(int i = 1 ; i <= n ; ++i){
    	cin >> a[i];
    	b.pb(a[i]);
	}
    sort(b.begin() , b.end());
    auto id = unique(b.begin() , b.end());
    b.resize(distance(b.begin() , id));
    
    for(int i = 1 ; i < b.size() ; ++i) cha[i] = i;
    
    int ptr = 0;
	for(int i = 1 ; i < b.size() ; ++i){
		if(dd[b[i]]) continue;
		for(int j = b[i] ; j <= 1e7 ; j += b[i]){
			dd[j] = 1;
			int p = lower_bound(b.begin() , b.end() , j) - b.begin();
			if(p < b.size()) e[++ptr] = {i , p , min(b[i] % b[p] , b[p] % b[i])};
			if(p + 1 < b.size()) e[++ptr] = {i , p + 1 , min(b[i] % b[p + 1] , b[p + 1] % b[i])};
		}
	}
	
	sort(e + 1 , e + 1 + ptr);
	int ans = 0;
	for(int i = 1 ; i <= ptr ; ++i){
		int u1 = find(e[i].u);
		int v1 = find(e[i].v);
		if(u1 == v1) continue;
		
		join(u1 , v1);
		ans += e[i].w;
	}
	
	cout << ans;
}

Compilation message

sirni.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main()
      | ^~~~
sirni.cpp: In function 'int main()':
sirni.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 1 ; i < b.size() ; ++i) cha[i] = i;
      |                     ~~^~~~~~~~~~
sirni.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 1 ; i < b.size() ; ++i){
      |                  ~~^~~~~~~~~~
sirni.cpp:59:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    if(p < b.size()) e[++ptr] = {i , p , min(b[i] % b[p] , b[p] % b[i])};
      |       ~~^~~~~~~~~~
sirni.cpp:60:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    if(p + 1 < b.size()) e[++ptr] = {i , p + 1 , min(b[i] % b[p + 1] , b[p + 1] % b[i])};
      |       ~~~~~~^~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9052 KB Output is correct
2 Correct 242 ms 75092 KB Output is correct
3 Correct 7 ms 10588 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 10320 KB Output is correct
2 Correct 1201 ms 440476 KB Output is correct
3 Correct 9 ms 11616 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9556 KB Output is correct
2 Correct 2 ms 6240 KB Output is correct
3 Correct 5 ms 10444 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 29876 KB Output is correct
2 Correct 448 ms 50656 KB Output is correct
3 Correct 468 ms 56136 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14536 KB Output is correct
2 Correct 311 ms 40396 KB Output is correct
3 Correct 299 ms 28060 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 41936 KB Output is correct
2 Correct 511 ms 57092 KB Output is correct
3 Correct 315 ms 40532 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 16088 KB Output is correct
2 Correct 518 ms 58324 KB Output is correct
3 Correct 426 ms 52200 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 42196 KB Output is correct
2 Correct 1793 ms 387792 KB Output is correct
3 Correct 293 ms 49872 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 52452 KB Output is correct
2 Correct 2117 ms 476300 KB Output is correct
3 Correct 730 ms 193488 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 14932 KB Output is correct
2 Correct 2266 ms 383440 KB Output is correct
3 Correct 470 ms 53968 KB Output is correct