제출 #1124835

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124835		Dreamy_lovesper	Sirni (COCI17_sirni)	C++20	42 / 140	105 ms	12876 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 1000'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;
        //
    }
};

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

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: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14