Submission #1190830

#TimeUsernameProblemLanguageResultExecution timeMemory
1190830aladdin1Sirni (COCI17_sirni)C++20
42 / 140
997 ms851968 KiB
#include <bits/stdc++.h> #define int long long #define ll long long #define ld long double #define all(v) v.begin(),v.end() #define INF 1000000000 using namespace std; const int MAX=4e5+100; const int N=3e5+5; const int MOD = 1e9 + 7; /* ---------------------------------------------------------------------------------- | BBBBBBBBBB LL BBBBBBBBBB DDDDDDDD DDDDDDD III N N | BB BB LL BB BB DD DD DD DD III NN N | BB BB LL BB BB DD DD DD DD III N N N | BBBBBBBBBB LL BBBBBBBBBB DD DD DD DD III N N N | BB BB LL BB BB DD DD DD DD III N N N | BB BB LL BB BB DD DD DD DD III N N N | BB BB LL BB BB DD DD DD DD III N NN | BB BB LLLLLLLL BB BB DDDDDDDD DDDDDDD III N N | | ---------------------------------------------------------------------------------- */ int par[MAX],sz[MAX]; int get(int a){ if(par[a]==-1)return a; return par[a]=get(par[a]); } bool unite(int a,int b){ a=get(a); b=get(b); if(a==b)return false; if(sz[a]>sz[b])swap(a,b); sz[b]+=sz[a]; par[a]=b; return true; } void solve(){ int n;cin>>n; vector<int>v(n+1); for(int i=1;i<=n;i++){ cin>>v[i]; } vector<array<int,3>>g; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ int cost; if(v[i]<=v[j])cost = min(v[i],v[j] % v[i]); else cost = min(v[j],v[i] % v[j]); g.push_back({cost,i,j}); } } sort(all(g)); memset(par,-1,sizeof(par)); fill(sz,sz + MAX,1); int ans=0,cnt=0; for(auto [w,a,b] : g){ if(unite(a,b)){ ans+=w; cnt++; if(cnt==n-1)break; } } cout<<ans<<endl; } signed main(){ int t=1;//cin>>t; while(t--){ solve(); } }
#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...