Submission #1191459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191459		TheSahib	Sirni (COCI17_sirni)	C++17	84 / 140	5107 ms	789684 KiB

sirni

#include <bits/stdc++.h>


using namespace std;
 
#define ll long long
#define all(v) v.begin(), v.end()
#define pii pair<int, int>

const int MAX = 1e5 + 100, MOD = 1e9 + 7, oo = 1e18;


int par[MAX],sz[MAX];
int get(int a){
    if(par[a]==-1)return a;
    return par[a]=get(par[a]);
}
bool unite(int a,int b){
    a=get(a);
    b=get(b);
    if(a==b)return false;
    if(sz[a]>sz[b])swap(a,b);
    sz[b]+=sz[a];
    par[a]=b;
    return true;
}

void solve(){
    memset(par, -1, sizeof(par));
    int n; cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        sz[i] = 1;
    }
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    vector<array<int, 3>> edges;
    for (int i = 0; i < v.size() - 1; i++)
    {
        int x = v[i];
        edges.push_back({v[i + 1] % v[i], i, i + 1});
        for(int l = x * 2; ; l += x){
            auto itr = lower_bound(all(v), l);
            if(itr == v.end()) break;
            edges.push_back({*itr % v[i], i, (int)(itr - v.begin())});
        }
    }
    sort(all(edges));
    int ans = 0;
    for(auto& e:edges){
        if(unite(e[1], e[2])){
            ans += e[0];
        }
    }
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

sirni.cpp:10:48: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   10 | const int MAX = 1e5 + 100, MOD = 1e9 + 7, oo = 1e18;
      |                                                ^~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14