oj.uz

Submission #248578

# Submission time Handle Problem Language Result Execution time Memory
248578 2020-07-12T19:02:34 Z Redhood Sirni (COCI17_sirni) C++14
0 / 140
 302 ms 287096 KB 
#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;
        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);
                }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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 274424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 274424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 161 ms 274424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 281792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 275948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 286148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 276320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 287096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 288 ms 285680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 198 ms 276860 KB Output isn't correct
2 Halted 0 ms 0 KB -