Submission #1164162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164162		KindaNameless	Sirni (COCI17_sirni)	C++20	140 / 140	1531 ms	746984 KiB

sirni

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

struct DSU{
    vector<int> par, sz;
    int N;

    DSU(int _N){
        N = _N;
        sz  = vector<int>(N + 5, 1);
        par = vector<int>(N + 5, 0);
        iota(par.begin(), par.end(), 0);
    }

    int rep(int x){
        if(x == par[x]){
            return x;
        }
        return par[x] = rep(par[x]);
    }

    bool comb(int u, int v){
        u = rep(u); v = rep(v);

        if(u != v){
            if(sz[u] > sz[v]){
                swap(u, v);
            }
            par[u] = v;
            sz[v] += sz[u];
            return 1;
        }
        return 0;
    }
};

void solve(){
    int N; cin >> N;

    int maximum = 0;
    vector<int> P;
    for(int i = 1; i <= N; ++i){
        int p; cin >> p;
        P.push_back(p);
        maximum = max(maximum, p);
    }

    sort(P.begin(), P.end());
    P.resize(unique(P.begin(), P.end()) - P.begin());

    vector<pair<int, int>> order;
    for(int i = 0; i < P.size(); ++i){
        order.push_back(make_pair(P[i], i));
    }

    vector<int> next(maximum + 1, -1);
    for(int i = 1, j = 0; i <= maximum && j < P.size(); ++i){
        while(j < P.size() && i > P[j]){
            j++;
        }
        next[i] = j;
    }

    DSU dsu(P.size());
    vector<vector<pair<int, int>>> edges(maximum + 1);

    for(int i = 0; i < P.size() - 1; ++i){
        int cur = P[i];
        edges[P[i + 1] % cur].push_back(make_pair(i, i + 1));
        for(int j = cur + cur; j <= maximum; j += cur){
            if(next[j] != -1){
                edges[P[next[j]] % cur].push_back(make_pair(i, next[j]));
            }
        }
    }

    ll answer = 0;
    for(int i = 0; i <= maximum; ++i){
        for(auto elem : edges[i]){
            if(dsu.comb(elem.first, elem.second)){
                answer += (ll)i;
            }
        }
    }

    cout << answer;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1; //cin >> tc;

    while(tc--){
        solve();
    }

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