oj.uz

Submission #715444

# Submission time Handle Problem Language Result Execution time Memory
715444 2023-03-26T18:05:35 Z TheSahib Sirni (COCI17_sirni) C++17
56 / 140
 1751 ms 311852 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 168 ms 278476 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 137412 KB Output is correct
2 Runtime error 1016 ms 279696 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 177 ms 278448 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 150940 KB Output is correct
2 Correct 1102 ms 177712 KB Output is correct
3 Correct 535 ms 155448 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 139432 KB Output is correct
2 Correct 329 ms 159644 KB Output is correct
3 Correct 409 ms 150548 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 162464 KB Output is correct
2 Correct 1751 ms 189144 KB Output is correct
3 Correct 404 ms 154416 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 141992 KB Output is correct
2 Correct 942 ms 186312 KB Output is correct
3 Correct 398 ms 153784 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 516 ms 311852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 508 ms 311572 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 213 ms 284516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -