Submission #715444

#	Time	Username	Problem	Language	Result	Execution time	Memory
715444		TheSahib	Sirni (COCI17_sirni)	C++17	56 / 140	1751 ms	311852 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) / 2;

int maxVal = 0;
set<int> s;

struct edge{
    int u, v;
};

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; scanf("%d", &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});
            }
        }
    }
    memset(par, -1, sizeof(par));
    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';
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:42:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         int a; scanf("%d", &a);
      |                ~~~~~^~~~~~~~~~

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