oj.uz

Submission #482365

# Submission time Handle Problem Language Result Execution time Memory
482365 2021-10-24T06:59:29 Z MilosMilutinovic Sirni (COCI17_sirni) C++14
0 / 140
 422 ms 51120 KB 
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define pb push_back

using namespace std;

int n;
int niz[100005];
int dsu[100005];

int finddsu(int x){
    if(dsu[x] == x)return x;
    return dsu[x] = finddsu(dsu[x]);
}
bool unite(int a, int b){
    a = finddsu(a);
    b = finddsu(b);
    if(a == b)return false;
    dsu[b] = a;
    return true;
}

struct edge{
    int u,v,w;
};
vector<edge> gr;

bool cmp(edge a, edge b){
    return a.w < b.w;
}

int get(int i){
    int l=1, r=n, pos;
    while(l <= r){
        int mid = (l + r) / 2;
        if(niz[mid] > i)pos = mid, r = mid-1;
        else l = mid+1;
    }
    return pos;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    ff(i,1,n)dsu[i] = i;
    ff(i,1,n)cin >> niz[i];
    sort(niz+1, niz+n+1);

    ff(i,1,n){
        int j = i;
        while(j+1 <= n && niz[j+1] == niz[i])j++;
        ff(x,i,j)unite(i, x);
        i = j;
    }

    ff(i,1,n){
        if(i > 1 && niz[i] == niz[i-1])continue;
        for(int j = niz[i]; j < niz[n]; j += niz[i]){
            int gde = get(j);
            gr.pb({i,gde,niz[gde] % niz[i]});
        }
    }
    sort(gr.begin(), gr.end(), cmp);
    long long ans = 0;
    for(auto c:gr){
        if(unite(c.u,c.v)){
            ans += c.w;
        }
    }
    cout << ans;


    return 0;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sirni.cpp:49:5: note: in expansion of macro 'ff'
   49 |     ff(i,1,n)dsu[i] = i;
      |     ^~
sirni.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sirni.cpp:50:5: note: in expansion of macro 'ff'
   50 |     ff(i,1,n)cin >> niz[i];
      |     ^~
sirni.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sirni.cpp:53:5: note: in expansion of macro 'ff'
   53 |     ff(i,1,n){
      |     ^~
sirni.cpp:2:27: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sirni.cpp:56:9: note: in expansion of macro 'ff'
   56 |         ff(x,i,j)unite(i, x);
      |         ^~
sirni.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sirni.cpp:60:5: note: in expansion of macro 'ff'
   60 |     ff(i,1,n){
      |     ^~
sirni.cpp: In function 'int get(int)':
sirni.cpp:40:12: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |     return pos;
      |            ^~~
sirni.cpp: In function 'int main()':
sirni.cpp:64:33: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |             gr.pb({i,gde,niz[gde] % niz[i]});
      |                          ~~~~~~~^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 191 ms 26472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 3648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 422 ms 51120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 7092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 250 ms 26520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 291 ms 26524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 3832 KB Output isn't correct
2 Halted 0 ms 0 KB -