Submission #1149673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149673		dantovisk	Sirni (COCI17_sirni)	C++20	0 / 140	227 ms	107692 KiB

sirni

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

#define int long long int
#define tiii tuple<int,int,int>

priority_queue <tiii, vector<tiii>, greater<tiii>> pq;
set <int> v;
int32_t ind[10000010];

map <int, int> indmap;

int par[510];
int sz[510];

int find(int a){
    if(a==par[a]) return a;
    return par[a] = find(par[a]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);

    if(sz[b] > sz[a]) swap(a,b);

    sz[a] += sz[b];
    par[b] = a;
}

int32_t main(){
    int n, m = 0;
    cin>>n;

    for(int i=0; i<n; i++){
        int a; cin>>a;
        v.insert(a);
        m = max(a, m);
    }

    //precomputaremos para todo valor i qual é o próximo
    //numero maior que i que aparece na entrada.

    int k = 0;
    for(auto x: v){
        while(k < x){
            ind[k] = x;
            k++;
        }
    }

    int z = 0;
    //gerando os pares "bons"
    for(auto x: v){
        indmap[x] = z;
        z++;
        for(int i=1; (i*x) < m; i++){
            pq.push({ind[i*x] % x, x, ind[i*x]});
        }
    }

    for(int i=0; i<=n; i++){
        par[i] = i;
        sz[i] = 1;
    }

    int resp = 0;


    while(!pq.empty()){
        auto [a,b,c] = pq.top();
        pq.pop();
        b = indmap[b];
        c = indmap[c];

        b = find(b);
        c = find(c);

        if(b == c) continue;
        resp+=a;
        merge(b, c);
    }

    cout<<resp<<"\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