Submission #1124910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124910		Dreamy_lovesper	Sirni (COCI17_sirni)	C++20	126 / 140	5118 ms	577584 KiB

sirni

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

#define LIFESUCKS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ll int
#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 = (1ll << 31);
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[100'007];


vector<pair<ll, ll>> edge[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;
    }
};

void lovesper(const ll TestCase){
    cin >> n;
    fu ( i, 1, n ) cin >> g[i];
    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 });
                j = *it / i * i;
            }
        }

        DSU dsu(mx + 1);
        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;
}

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;
}

Compilation message (stderr)

sirni.cpp:8: warning: "ll" redefined
    8 | #define ll int
      | 
sirni.cpp:7: note: this is the location of the previous definition
    7 | #define ll long long
      | 
sirni.cpp:20:21: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
   20 | const ll lnf = (1ll << 60);
      |                ~~~~~^~~~~~

• 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: 0 / 14
• Subtask 10: 14 / 14