Submission #715440

#	Time	Username	Problem	Language	Result	Execution time	Memory
715440		TheSahib	Sirni (COCI17_sirni)	C++17	112 / 140	5080 ms	664516 KiB

sirni

#include <bits/stdc++.h>


#define ll long long
#define pii pair<int, int>

using namespace std;

const int MAX = 1e5 + 5;
const int MAXVAL = 1e7 + 7;

int maxVal = 0;
set<int> s;

struct edge{
    int u, v, weight;
    bool operator<(edge e){
        return weight < e.weight;
    }
};

int par[MAXVAL];
vector<edge> edges[MAXVAL];
int findPar(int u){
    if(par[u] < 0) return u;
    return par[u] = findPar(par[u]);
}

bool setUnion(int u, int v){
    u = findPar(u);
    v = findPar(v);
    if(u == v) return false;

    if(-par[u] < -par[v]) swap(u, v);
    par[u] += par[v];
    par[v] = u;
    
    return true;
}

int main(){
    int n; cin >> n;
    for (int i = 0; i < n; i++)
    {
        int a; cin >> a;
        s.insert(a);
    }
    maxVal = *(prev(s.end()));
    for(int a:s){
        if(a == maxVal) continue;
        for(int j = a; j <= maxVal; j += a){
            int b = 0;
            if(j == a){
                b = *s.upper_bound(j);
            }
            else{
                b = *s.lower_bound(j);
            }
            if((b / a) == (j / a)){
                edges[b % a].push_back({a, b, b % a});
            }
        }
    }
    fill(par, par + maxVal + 1, -1);
    ll cost = 0;
    for (int i = 0; i <= maxVal; i++)
    {
        for(edge& e:edges[i]){
            if(setUnion(e.u, e.v)){
                cost += i;
            }
        }
    }
    
    cout << cost << '\n';
}

• 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: 0 / 14
• Subtask 10: 0 / 14