Submission #989542

#	Time	Username	Problem	Language	Result	Execution time	Memory
989542		re4ler	Sirni (COCI17_sirni)	C++17	140 / 140	2266 ms	476300 KiB

sirni

#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 (stderr)

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 / 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