Submission #1124913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124913		Dreamy_lovesper	Sirni (COCI17_sirni)	C++20	126 / 140	4628 ms	577140 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 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;
    set<int> st;
    ll mx = 0;
    for(int i = 1; i <= n; i++){
        ll x; cin >> x;
        mx = max(mx, x);
        st.insert(x);
    }
    for(int i : st){
        auto itt = st.upper_bound(i);
        if(itt != st.end()) edge[*itt % i].push_back({i, *itt});
        for(int j = i * 2; j <= mx; j += i){
            auto it = st.lower_bound(j);
            if(it != st.end()){
                edge[*it % i].push_back({i, *it});
                j = *it / i * i;
            }
        }
    }
    ll sad= 0;
    DSU t(mx);
    for(int i = 0; i <= 1e7; i++){
        for(auto  j : edge[i]){
            sad += t.suion(j.first, j.second) * 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:7: warning: "ll" redefined
    7 | #define ll int
      | 
sirni.cpp:6: note: this is the location of the previous definition
    6 | #define ll long long
      | 
sirni.cpp:19:21: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
   19 | const ll lnf = (1ll << 60);
      |                ~~~~~^~~~~~

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