제출 #1190830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190830		aladdin1	Sirni (COCI17_sirni)	C++20	42 / 140	997 ms	851968 KiB

sirni

#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();
    }
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 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