Submission #715243

#TimeUsernameProblemLanguageResultExecution timeMemory
715243FidanSirni (COCI17_sirni)C++17
42 / 140
414 ms786432 KiB
#include <bits/stdc++.h> using namespace std; using ll=long long; using ld=long double; #define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++) #define repn(i, a, b) for(ll i=ll(b)-1; i>=a; i--) #define ff first #define ss second #define all(x) x.begin(), x.end() #define sz(x) x.size() #define bg begin() #define ed end() #define pb push_back struct DSU { vector<ll> e; DSU(ll n){ e=vector<ll> (n, -1); } ll get(ll x){ return e[x]<0 ? x: e[x]=get(e[x]); } bool same_set(ll a, ll b){ return get(a)==get(b); } ll size(ll x){ return -e[get(x)]; } bool unite(ll a, ll b){ a=get(a), b=get(b); if(a==b) return false; if(e[a]>e[b]) swap(a, b); e[a]+=e[b], e[b]=a; return true; } }; void solve(){ ll n; cin>>n; vector<ll> q(n); rep(i, 0, n){ cin>>q[i]; } sort(all(q)); vector<ll> p; p.pb(q[0]); rep(i, 1, n){ if(q[i]==q[i-1]) continue; p.pb(q[i]); } n=p.size(); if(n==1){ cout<<0; } else{ DSU dsu(n); vector<vector<ll>> v(n, vector<ll>(n)); set<pair<ll, pair<ll, ll>>> s; rep(i, 0, n){ rep(j, i+1, n){ v[i][j]=min(p[i]%p[j], p[j]%p[i]); v[j][i]=min(p[i]%p[j], p[j]%p[i]); s.insert({v[i][j], {i, j}}); } } ll sum=0, c=n-1; while(c>0){ auto a=(*s.begin()); s.erase(s.begin()); ll a1=a.ff; auto b=a.ss; ll b1=b.ff, b2=b.ss; if(dsu.same_set(b1, b2)) continue; c--; sum+=a1; dsu.unite(b1, b2); } cout<<sum; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll t=1; //~ cin>>t; while(t--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...