Submission #482365

#	Time	Username	Problem	Language	Result	Execution time	Memory
482365		MilosMilutinovic	Sirni (COCI17_sirni)	C++14	0 / 140	422 ms	51120 KiB

sirni

#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 (stderr)

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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14