Submission #947567

#	Time	Username	Problem	Language	Result	Execution time	Memory
947567		lambd47	Sirni (COCI17_sirni)	C++14	140 / 140	4481 ms	401380 KiB

sirni

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+7;
int pai[MAXN];
int tam[MAXN];
vector<int> v;
struct aresta{
    int peso,a,b;
    bool operator<(aresta aux)const{
        return peso<aux.peso;
    }
};
vector<aresta> adj;
int resp=0;
int find(int pos){
    if(pos==pai[pos])return pos;
    return pai[pos]=find(pai[pos]);
}
bool uni(int a, int b){
    a=find(a);
    b=find(b);
    if(a==b)return false;
    if(tam[a]<tam[b])swap(a,b);
    tam[a]+=b;
    pai[b]=a;
    return true;
}

void prim(){
    for(auto e:adj){
        if(uni(e.a,e.b))resp+=e.peso;
    }
}

int main(){
    int n;
    cin>>n;
    set<int> s;
    for(int i=0;i<=n;i++){
        pai[i]=i;
        tam[i]=1;
    }
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(a!=1){
        s.insert(a);
        }
        else{
            cout<<0;
            return 0;
        }
    } 
    for(auto a:s)v.push_back(a);
      
    int M=v.back();
    int t=v.size();
    for(int i=0;i<t;i++){
        int passado=-1;
        for(int j=2;j*v[i]<=M;j++){
            auto pt=lower_bound(v.begin(),v.end(),j*v[i]);
            int x=*pt;
            int k=pt-v.begin();
            //cout<<v[i]<<" "<<j<<" "<<x<<" "<<k<<"\n";
            if(x!=passado){
            adj.push_back({(x)%v[i],i,k});
            passado=x;
            }
        }
        if(i!=t-1){
            if(v[i+1]<2*v[i]){
            adj.push_back({v[i+1]%v[i],i,i+1});
            }
        }
    }
    sort(adj.begin(),adj.end());
    /*cout<<":::::::::::::::::\n";
    for(auto [a,b,c]: adj)cout<<a<<" "<<b<<" "<<c<<"\n";*/
    prim();
    cout<<resp;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14