Submission #1164202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164202		altern23	Sirni (COCI17_sirni)	C++20	0 / 140	647 ms	507536 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#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, sz;
    DSU(ll _n){
        n = _n;
        par.resize(n + 5), sz.resize(n + 5);
        for(int i = 1; i <= n; i++){
            par[i] = i, sz[i] = 1;
        }
    }

    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;
        if(sz[a] < sz[b]) swap(a, b);
        par[b] = a;
        sz[a] += sz[b];
        sz[b] = 0;
        return true;
    }
};

vector<pii> edges[N + 5];
ll sf[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;
        vector<ll> a(n + 5);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            sf[a[i]] = a[i];
        }

        for(int i = N; i >= 1; --i){
            if(sf[i] != i) sf[i] = sf[i + 1];
        }
        
        DSU dsu(N);

        for(ll i = 1; i <= N; i++){
            if(sf[i] != i) continue;
            for(ll j = i; j <= N; j += i){
                if(sf[j] == j){
                    dsu.join(i, j);
                }
                else if(sf[j]){
                    edges[sf[j] % i].push_back({i, sf[j]});
                }
            }
        }

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

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

/*

*/ 

• 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