Submission #1139325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139325		ChottuF	Sirni (COCI17_sirni)	C++20	0 / 140	11 ms	3648 KiB

sirni

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;
    int c;
    DSU(int n):p(n),sz(n,1),c(n){
        for(int i=0;i<n;i++)p[i]=i;
    }
    int f(int x){return p[x]==x?x:p[x]=f(p[x]);}
    bool u(int a,int b){
        a=f(a);b=f(b);
        if(a==b)return false;
        if(sz[a]<sz[b])swap(a,b);
        p[b]=a;sz[a]+=sz[b];c--;return true;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;cin>>N;vector<long long> A(N);for(int i=0;i<N;i++)cin>>A[i];
    static vector<int> idx[100001];for(int i=0;i<=100000;i++)idx[i].clear();
    long long mx=0;for(int i=0;i<N;i++){mx=max(mx,A[i]);idx[A[i]].push_back(i);}
    DSU dsu(N);
    for(int v=0;v<=100000;v++){
        if(idx[v].size()>1){
            for(int j=1;j<(int)idx[v].size();j++){
                dsu.u(idx[v][0],idx[v][j]);
            }
        }
    }
    vector<int> rep(100001,-1);
    for(int v=0;v<=100000;v++){
        if(!idx[v].empty())rep[v]=idx[v][0];
    }
    vector<long long> distinct;
    for(int v=0;v<=mx;v++){
        if(rep[v]!=-1)distinct.push_back(v);
    }
    vector<array<long long,3>> edges;
    auto addE=[&](long long x,long long y){
        if(x==y)return;
        long long c1=x%y,c2=y%x;edges.push_back({min(c1,c2),rep[x],rep[y]});
    };
    sort(distinct.begin(),distinct.end());
    for(long long x:distinct){
        if(x==0)continue;
        for(long long m=x;m<=mx;m+=x){
            auto it=lower_bound(distinct.begin(),distinct.end(),m);
            if(it!=distinct.begin())addE(x,*(it-1));
            if(it!=distinct.end())addE(x,*it);
        }
    }
    sort(edges.begin(),edges.end(),[&](auto&a,auto&b){return a[0]<b[0];});
    long long ans=0;
    for(auto&e:edges){
        if(dsu.u(e[1],e[2])){ans+=e[0];if(dsu.c==1)break;}
    }
    cout<<ans<<"\n";
    return 0;
}

• 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