Submission #248580

#	Time	Username	Problem	Language	Result	Execution time	Memory
248580		Redhood	Sirni (COCI17_sirni)	C++14	140 / 140	1202 ms	368412 KiB

sirni

#include<bits/stdc++.h>

#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
#define len(x) (int)(x).size()
#define pb push_back
using namespace std;
typedef pair<int,int > pii;
typedef long long ll;
typedef long double ld;
const int N = 1e5;
int s[N], p[N];
void make(int v){
    p[v] = v ;
    s[v] = 1;
}
int fin(int v){
    if(p[v] == v)return v;
    return p[v] = fin(p[v]);
}
void un(int a , int b){
    a = fin(a) , b = fin(b);
    if(a == b)return;
    if(s[a] < s[b])swap(a , b);
    p[b]  = a , s[a] += s[b];
}
const int NN = (int)1e7 + 1;
int great[NN];


vector<pii> Edges[NN];
signed main(){
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int n;cin >> n;
    vector<int>p(n);
    for(auto &i : p)cin >> i;
    sort(all(p));
    p.erase(unique(all(p)) , p.end());
    n = len(p);
    for(int i = 0 ; i< n; ++i)
        make(i);

   int  lst = n - 1;
    for(int j = NN - 1; j >=0 ; --j){
        while(lst  - 1>= 0 && p[lst - 1] >= j)
            --lst;
        if(j > p[n-1])
            great[j]=-1;
        else
        great[j] = lst;
    }
    for(int i = 0 ; i < n; ++i){
        if(fin(i) == i){
            int prev = -1;
            for(int j = (p[n-1]/p[i])*p[i]; j >= 0; j -= p[i]){
                int cur = great[j];
                if(cur == prev)continue;
                if(p[cur] == j){
                    un(i , cur);
                    if(great[j+1] != prev){
                        int cur1 = great[j+1];
                        Edges[p[cur1]-j].pb({i , cur1});
                    }
                }else
                    Edges[p[cur]-j].pb({i , cur});
                prev = cur;
            }
        }
    }
    ll answer = 0;
    for(int i = 0 ;i < NN; ++i){
        for(auto u : Edges[i]){
            if(fin(u.fi) != fin(u.se)){
                un(u.fi , u.se);
                answer += i;
            }
        }
    }
    int lead = fin(0);
    for(int i =  0; i < n; ++i)
        assert(fin(i) == lead);
    cout << answer << '\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: 14 / 14
• Subtask 10: 14 / 14