제출 #1124914

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124914		Dreamy_lovesper	Sirni (COCI17_sirni)	C++20	112 / 140	4978 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 = (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(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;
                }
            }
        }

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

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