제출 #1190928

#제출 시각아이디문제언어결과실행 시간메모리
1190928hikari1234Sirni (COCI17_sirni)C++20
42 / 140
892 ms851968 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define ff first #define ss second int n; int a[100005]; vector<pair<int,pair<int,int>>> edges; int sz[100005], par[100005]; int fin(int x){ if(par[x]==x) return x; return par[x]=fin(par[x]); } bool unite(int x, int y){ x=fin(x), y=fin(y); if(x==y) return 0; if(sz[y]>sz[x]) swap(x,y); sz[x]+=sz[y]; par[y]=x; return 1; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin>>n; for(int i=1; i<=n; i++){ cin>>a[i]; sz[i]=1; par[i]=i; } sort(a+1,a+n+1); for(int i=1; i<=n; i++){ for(int j=i+1; j<=n; j++){ edges.push_back({min(a[i]%a[j],a[j]%a[i]),{i,j}}); } } int ans=0; sort(edges.begin(),edges.end()); for(pair<int,pair<int,int>> &i: edges){ if(unite(i.ss.ff,i.ss.ss)){ ans+=i.ff; } } cout<<ans<<endl; }
#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...