Submission #1124439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124439		codexistent	Sirni (COCI17_sirni)	C++20	98 / 140	5126 ms	793752 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100005
#define MAXL 10000005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)

ll n, r = 0, p[MAXN], sz[MAXN];
vector<ll> v;
vector<pair<ll, pair<ll, ll>>> e;

void compress(){
    set<ll> s(begin(v), end(v));
    v.assign(begin(s), end(s));
}

ll find(ll x){
    return (x == p[x]) ? x : (p[x] = find(p[x]));  
}

bool onion(ll a, ll b){
    a = find(a), b= find(b);
    if(a == b) return false;

    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    p[a] = p[b] = a;
    return true;
}

int main(){
    cin >> n;
    FOR(i, 1, n) {
        ll x; cin >> x;
        v.push_back(x);
    }
    compress();

    n = v.size();
    FOR(i, 1, n - 1) e.push_back({v[i] % v[i - 1], {i - 1, i}});
    FOR(i, 0, n - 1){
        for(ll j = v[i]; j <= MAXL; ){
            ll lo = i + 1, hi = n;
            while(lo < hi){
                ll md = (lo + hi) / 2;
                if(md == n || j <= v[md]){
                    hi = md;
                }else{
                    lo = md + 1;
                }
            }

            if(hi == n) break;

            e.push_back({v[lo] % v[i], {lo, i}});
            j = v[lo] / v[i] * v[i] + v[i];
        }
    }

    sort(begin(e), end(e));
    FOR(i, 0, n - 1) p[i] = i, sz[i] = 1;
    for(auto ei : e){
        r += onion(ei.second.first, ei.second.second) * ei.first;
    }
    cout << r << endl;
}

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