Submission #1124893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124893		Dreamy_lovesper	Sirni (COCI17_sirni)	C++20	84 / 140	4437 ms	851968 KiB

sirni

#include<bits/stdc++.h>

using namespace std;

#define LIFESUCKS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
#define fi first
#define se second
#define all(c) c.begin(),c.end()
#define debug cout<<"I Love You\n";
#define Bitc(x, j) ((x >> j) & 1)
#define fu(i,a,b) for ( int i = a; i <= b; i++ )
#define fd(i,b,a) for ( int i = b; i >= a; i-- )

const ll Mod = 1e9+7;
const ll inf = 1e15;
const ll lnf = (1ll << 60);

template <class X, class Y>
    bool minimize (X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize (X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }

#define mxn 10'000'007

ll n, g[mxn];

struct DSU {
    ll n;
    vector<ll> par;
    DSU ( ll _n ) {
        this ->n = _n;
        par.resize(n);
        iota(all(par), 0);
    }
    ll find ( ll v ) {
        return v == par[v] ? v : par[v] = find(par[v] );
    }
    ll suion ( ll u, ll v ) {
        u = find(u); v= find(v);
        if ( u == v ) return 0;
        par[v] = u;
        return 1;
    }
};

namespace Love1{
    bool check() {
        return n <= 10000;
    }

    struct Edge {
        ll u, v, w;
        bool operator < ( const Edge&other ) const {
            return other.w < w;
        }
    };

    void DreamyLove() {
        priority_queue<Edge> Q;
        fu ( u, 1, n )
            fu ( v, u + 1, n ) {
                ll w = min ( g[u] % g[v], g[v] % g[u] );
                Q.push({ u, v, w});
            }
        DSU dsu( n + 7 );
        ll sad = 0;
        while ( !Q.empty() ) {
            ll u = Q.top().u;
            ll v = Q.top().v;
            ll w = Q.top().w;
            Q.pop();
            if ( dsu.suion( u, v)) sad += w;
        }
        cout << sad;
        //
    }
};

namespace LoveLast{
    vector<pair<ll, ll>> edge[mxn];
    void DreamyLove() {

        set<ll> st;
        ll mx = 0;
        fu ( i, 1, n ) {
            maximize( mx, g[i] );
            st.insert(g[i]);
        }

        for ( auto& i: st ) {
            auto _it = st.upper_bound ( i );
            if ( _it != st.end() ) edge[ *_it % i ].pb({ i, *_it });
            for ( ll j = i * 2; j <= mx; j += i ) {
                auto it = st.lower_bound( j );
                if ( it == st.end() ) continue;
                edge[ *it % i ].pb({ i, *it });
            }
        }

        DSU dsu(mx + 3);
        ll sad = 0;
        fu ( i, 0, 1e7 )
            for ( pair<ll, ll>& it: edge[i] ) {
                ll u = it.fi, v = it.se;
                sad += dsu.suion( u, v ) * i;
            }
        cout << sad;
        //
    }
}

void lovesper(const ll TestCase){
    cin >> n;
    fu ( i, 1, n ) cin >> g[i];
//    if (Love1::check() ){
//        Love1::DreamyLove();
//        return;
//    }
    LoveLast::DreamyLove();
}

signed main(){
    LIFESUCKS
    #define name "lovesper"
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);

    ll test=1;
//    cin >> test;
    for (int i = 1; i <= test; i++){
        lovesper(i);
        if ( i < test ) cout << '\n';
    }
    return 0;
}

• 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