Submission #1130180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130180		lowkeyad	Sirni (COCI17_sirni)	C++20	0 / 140	566 ms	178036 KiB

sirni

#include<bits/stdc++.h>
#define Lowkey ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define nmax 1000001
#define N 10000001
#define mod 1000000007
#define fi first
#define se second
#define task "___"
#define ii pair<long long , long long>
using namespace std;

void fre(){
	freopen(task".INP","r",stdin);freopen(task".OUT","w",stdout);
}

struct Edge{
	long long u , v , w;
	
	Edge(long long _u , long long _v , long long _w) : u(_u) , v(_v) , w(_w) {};
};

struct dsu{
	vector<long long> par , sz;
	
	void make_set(long long n){
		par.resize(n + 5 , 0);
		sz.resize(n + 5 , 0);
		for(int i = 1;i <= n;i++){
			par[i] = i;
			sz[i] = 1;
		}
	}
	
	long long find(long long v){
		if(par[v] == v){
			return v;
		}
		
		long long x = find(par[v]);
		
		par[v] = x;
		
		return x;
	}
	
	bool union_set(long long u , long long v){
		long long a = find(u) , b = find(v);
		
		if(a == b){
			return false;
		}
		
		if(sz[a] < sz[b]){
			swap(a , b);
		}
		
		par[b] = a;
		sz[a]+=sz[b];
		
		return true;
	}
} dsu;

long long p[nmax] , premx[N];
vector<Edge> edges;

bool cmp(Edge a , Edge b){
	return a.w < b.w;
}

int main(){
    Lowkey
	memset(premx , -1 , sizeof(premx));
	long long n , i , mx = 0;
	
	cin >> n;
	
	for(i = 1;i <= n;i++){
		cin >> p[i];
		
		mx = max(mx , p[i]);
	}
	
	sort(p + 1 , p  + n + 1);
	
	for(i = 1;i <= n;i++){
		premx[p[i]] = i;
	}
	
	for(i = mx - 1;i > 0;i--){
		if(premx[i] == -1){
			premx[i] = premx[i + 1];
		}
	}
	
	p[n + 1] = -1;
	
	for(i = 1;i < n;i++){
		if(p[i] == p[i + 1]){
			continue;
		}
		edges.push_back({ i , i + 1 , p[i + 1]%p[i] });
		
		for(int j = 2 * p[i] ; j <= mx;j+=p[i]){
			long long op = premx[j];
			
			edges.push_back({i , op , p[op] % p[i]});
		}
	}
	
	sort(edges.begin() , edges.end() , cmp);
	
	dsu.make_set(n);
	
	long long res = 0;
	
	for(auto e : edges){
		if(!dsu.union_set(e.u , e.v)){
			continue;
		}
		
		res += e.w;
	}
	
	cout << res;
}

Compilation message (stderr)

sirni.cpp: In function 'void fre()':
sirni.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen(task".INP","r",stdin);freopen(task".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:13:46: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen(task".INP","r",stdin);freopen(task".OUT","w",stdout);
      |                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14