Submission #1164236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164236		altern23	Sirni (COCI17_sirni)	C++20	84 / 140	1006 ms	851968 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];
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;
        vector<ll> a(n + 5);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            isi.push_back(a[i]);
        }

        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] = isi[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[nxt[j] % isi[i]].push_back({nxt[j], isi[i]});
                }
            }
        }

        for(int i = 1; i < isi.size(); i++){
            edges[isi[i] % isi[i - 1]].push_back({isi[i], isi[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";
    }   
}

/*

*/ 

• 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