oj.uz

Submission #947567

# Submission time Handle Problem Language Result Execution time Memory
947567 2024-03-16T12:11:54 Z lambd47 Sirni (COCI17_sirni) C++14
140 / 140
 4481 ms 401380 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 54 ms 3552 KB Output is correct
3 Correct 3 ms 800 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 390 ms 1380 KB Output is correct
3 Correct 3 ms 604 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 21328 KB Output is correct
2 Correct 499 ms 55736 KB Output is correct
3 Correct 238 ms 32808 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4544 KB Output is correct
2 Correct 246 ms 51736 KB Output is correct
3 Correct 154 ms 20128 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 56292 KB Output is correct
2 Correct 680 ms 105232 KB Output is correct
3 Correct 224 ms 33580 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 9540 KB Output is correct
2 Correct 615 ms 104308 KB Output is correct
3 Correct 204 ms 32056 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 33580 KB Output is correct
2 Correct 3251 ms 401380 KB Output is correct
3 Correct 234 ms 33020 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 33976 KB Output is correct
2 Correct 4481 ms 400248 KB Output is correct
3 Correct 373 ms 32308 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6348 KB Output is correct
2 Correct 4184 ms 399848 KB Output is correct
3 Correct 225 ms 32816 KB Output is correct