Submission #715446

#	Time	Username	Problem	Language	Result	Execution time	Memory
715446		TheSahib	Sirni (COCI17_sirni)	C++17	140 / 140	3440 ms	573544 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;
int arr[MAX];

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++)
    {
        scanf("%d", &arr[i]);
    }
    sort(arr, arr + n);
    maxVal = arr[n - 1];
    for(int i = 0; i < n; i++){
        if(i != 0 && arr[i - 1] == arr[i]) continue;
        int a = arr[i];
        if(a == maxVal) continue;
        for(int j = a; j <= maxVal; j += a){
            int b = 0;
            if(j == a){
                b = *upper_bound(arr, arr + n, j);
            }
            else{
                b = *lower_bound(arr, arr + n, 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 >> 1); 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:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

• 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