oj.uz

Submission #248580

# Submission time Handle Problem Language Result Execution time Memory
248580 2020-07-12T19:08:56 Z Redhood Sirni (COCI17_sirni) C++14
140 / 140
 1202 ms 368412 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;
        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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 274552 KB Output is correct
2 Correct 203 ms 276728 KB Output is correct
3 Correct 158 ms 274680 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 274424 KB Output is correct
2 Correct 200 ms 274500 KB Output is correct
3 Correct 170 ms 274552 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 274544 KB Output is correct
2 Correct 162 ms 274424 KB Output is correct
3 Correct 162 ms 274552 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 282848 KB Output is correct
2 Correct 242 ms 289012 KB Output is correct
3 Correct 234 ms 287852 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 276088 KB Output is correct
2 Correct 223 ms 287064 KB Output is correct
3 Correct 199 ms 282576 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 287528 KB Output is correct
2 Correct 237 ms 286588 KB Output is correct
3 Correct 203 ms 282864 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 276800 KB Output is correct
2 Correct 229 ms 286308 KB Output is correct
3 Correct 238 ms 286056 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 287600 KB Output is correct
2 Correct 528 ms 332016 KB Output is correct
3 Correct 311 ms 290588 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 286576 KB Output is correct
2 Correct 821 ms 342200 KB Output is correct
3 Correct 343 ms 294512 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 276984 KB Output is correct
2 Correct 1202 ms 368412 KB Output is correct
3 Correct 224 ms 287212 KB Output is correct