oj.uz

답안 #715446

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715446 2023-03-26T18:10:02 Z TheSahib Sirni (COCI17_sirni) C++17
140 / 140
 3440 ms 573544 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;

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 274492 KB Output is correct
2 Correct 180 ms 276724 KB Output is correct
3 Correct 132 ms 274536 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 274356 KB Output is correct
2 Correct 816 ms 274932 KB Output is correct
3 Correct 131 ms 274400 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 274404 KB Output is correct
2 Correct 128 ms 274236 KB Output is correct
3 Correct 129 ms 274428 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 234 ms 283804 KB Output is correct
2 Correct 504 ms 310988 KB Output is correct
3 Correct 297 ms 289168 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 139 ms 275828 KB Output is correct
2 Correct 283 ms 296508 KB Output is correct
3 Correct 231 ms 284116 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 391 ms 295108 KB Output is correct
2 Correct 619 ms 322244 KB Output is correct
3 Correct 278 ms 287532 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 277468 KB Output is correct
2 Correct 565 ms 320360 KB Output is correct
3 Correct 272 ms 287188 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 286536 KB Output is correct
2 Correct 2513 ms 482820 KB Output is correct
3 Correct 333 ms 288952 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 288 ms 286364 KB Output is correct
2 Correct 3440 ms 573544 KB Output is correct
3 Correct 452 ms 292852 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 276556 KB Output is correct
2 Correct 2898 ms 569124 KB Output is correct
3 Correct 286 ms 289336 KB Output is correct