Submission #1164259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164259		altern23	Sirni (COCI17_sirni)	C++17	140 / 140	1678 ms	747016 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
 
#define ll int
#define pii pair<ll, ll>
#define fi first
#define sec second

const ll N = 1e7;
const ll INF = 4e18;
const ll MOD = 1e9 + 7;

struct DSU{
    ll n;
    vector<ll> par;
    DSU(ll _n){
        n = _n;
        par.resize(n + 5);
        for(int i = 1; i <= n; i++){
            par[i] = i;
        }
    }

    ll find(ll idx){
        if(par[idx] == idx) return idx;
        return par[idx] = find(par[idx]);
    }

    bool join(ll a, ll b){
        a = find(a), b = find(b);
        if(a == b) return false;
        par[b] = a;
        return true;
    }
};

vector<pii> edges[N + 5];
vector<ll> isi;
ll nxt[N + 5];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n; cin >> n;
        for(int i = 1; i <= n; i++){
            ll x; cin >> x;
            isi.push_back(x);
        }

        sort(isi.begin(), isi.end());
        isi.erase(unique(isi.begin(), isi.end()), isi.end());

        ll cur = 0;
        for(int i = 1; i <= N; i++){
            while(cur < isi.size() && isi[cur] < i) cur++;
            if(cur < isi.size()) nxt[i] = cur;
        }

        DSU dsu(n);

        for(int i = 0; i < isi.size(); i++){
            for(ll j = isi[i]; j <= N; j += isi[i]){
                if(nxt[j]){
                    edges[isi[nxt[j]] % isi[i]].push_back({i, nxt[j]});
                }
            }
        }

        for(int i = 1; i < isi.size(); i++){
            edges[isi[i] % isi[i - 1]].push_back({i, i - 1});
        }

        ll ans = 0;
        for(ll i = 0; i <= N; i++){
            for(auto [x, y] : edges[i]){
                ans += dsu.join(x, y) * i;
            }
        }

        cout << ans << "\n";
    }   
}

/*

*/ 

Compilation message (stderr)

sirni.cpp:10:16: warning: overflow in conversion from 'double' to 'int' changes value from '4.0e+18' to '2147483647' [-Woverflow]
   10 | const ll INF = 4e18;
      |                ^~~~

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