Submission #470840

#	Time	Username	Problem	Language	Result	Execution time	Memory
470840		SirCovidThe19th	Sirni (COCI17_sirni)	C++17	0 / 140	353 ms	293036 KiB

sirni

#include <bits/stdc++.h>
using namespace std; 

const int mN = 1e5 + 5, mP = 1e7 + 5;

int n, mx, ub[mP], par[mP], sz[mP]; long long ans; vector<int> A; vector<pair<int, int>> edg[mP];

int get(int i){
    return (i == par[i]) ? i : par[i] = get(par[i]);
}
void merge(int a, int b, int w){
    a = get(a); b = get(b); if (a == b) return;
    if (a > b) swap(a, b);
    par[a] = b; sz[b] += sz[a]; ans += w;
}

int main(){
    cin >> n; A.resize(n);
    for (int &i : A) cin >> i;
    sort(A.begin(), A.end()); A.erase(unique(A.begin(), A.end()), A.end());
    n = A.size(); mx = A.back(); iota(par, par + n, 0); fill(sz, sz + n, 1);

    for (int i = 0; i < n; i++) ub[A[i]] = i;
    for (int i = mx, cur; i >= 0; i--) (ub[i]) ? cur = ub[i] : ub[i] = cur;

    for (int i = 0; i < n; i++)
        for (int x = A[i] * 2; x <= mx; x += A[i])
            edg[A[ub[x]] % x].push_back({i, ub[x]});
    for (int i = 0; i < mx; i++)
        for (auto edge : edg[i])
            merge(edge.first, edge.second, i);
    cout<<ans<<endl;
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:24:70: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   24 |     for (int i = mx, cur; i >= 0; i--) (ub[i]) ? cur = ub[i] : ub[i] = cur;
      |                                                                ~~~~~~^~~~~

• 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