oj.uz

Submission #152337

# Submission time Handle Problem Language Result Execution time Memory
152337 2019-09-07T15:25:23 Z alexandra_udristoiu Sirni (COCI17_sirni) C++14
140 / 140
 3260 ms 246952 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#define DIM 100005
using namespace std;
int n, i, j, r1, r2, p;
long long sol;
int v[DIM], r[DIM], nxt[10000005];
char viz[10000005];
struct str{
    int f, s, c;
};
vector<str> w;
int cmp(str a, str b){
    return a.c < b.c;
}
int rad(int x){
    int y = x;
    while(r[y] > 0){
        y = r[y];
    }
    while(r[x] > 0){
        int aux = r[x];
        r[x] = y;
        x = aux;
    }
    return x;
}
int main(){
    cin>> n;
    for(i = 1; i <= n; i++){
        cin>> v[i];
    }
    sort(v + 1, v + n + 1);
    p = 1;
    for(i = 2; i <= n; i++){
        if(v[i] != v[p]){
            v[++p] = v[i];
        }
    }
    if(v[1] == 1){
        cout<< 0;
        return 0;
    }
    n = p;
    for(i = 1; i <= n; i++){
        nxt[ v[i] ] = i;
    }
    for(i = v[n]; i >= v[1]; i--){
        if(nxt[i] == 0){
            nxt[i] = nxt[i + 1];
        }
    }
    for(i = 1; i < n; i++){
        if(v[i + 1] < 2 * v[i]){
            w.push_back( {i + 1, i, v[i + 1] % v[i]} );
        }
    }
    for(i = 1; i < n; i++){
        if(viz[ v[i] ] == 1){
            continue;
        }
        p = i + 1;
        for(j = v[i] + v[i]; j <= v[n]; j += v[i]){
            viz[j] = 1;
            p = nxt[j];
            if(v[p] < j + v[i]){
                w.push_back( {p, i, v[p] % v[i]} );
                p++;
            }
        }
    }
    sort(w.begin(), w.end(), cmp);
    for(i = 1; i <= n; i++){
        r[i] = -1;
    }
    for(i = 0; i < w.size(); i++){
        r1 = rad(w[i].f);
        r2 = rad(w[i].s);
        if(r1 != r2){
            sol += w[i].c;
            if(r[r1] < r[r2]){
                r[r1] += r[r2];
                r[r2] = r1;
            }
            else{
                r[r2] += r[r1];
                r[r1] = r2;
            }
        }
    }
    cout<< sol;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:77:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 0; i < w.size(); i++){
                ~~^~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 47480 KB Output is correct
2 Correct 353 ms 52240 KB Output is correct
3 Correct 79 ms 49400 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 356 ms 49436 KB Output is correct
3 Correct 79 ms 49656 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 47992 KB Output is correct
2 Correct 75 ms 44640 KB Output is correct
3 Correct 78 ms 49328 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 18136 KB Output is correct
2 Correct 268 ms 30440 KB Output is correct
3 Correct 244 ms 30408 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8552 KB Output is correct
2 Correct 261 ms 30276 KB Output is correct
3 Correct 157 ms 15640 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 30408 KB Output is correct
2 Correct 249 ms 30368 KB Output is correct
3 Correct 178 ms 18008 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 4712 KB Output is correct
2 Correct 248 ms 30540 KB Output is correct
3 Correct 242 ms 18124 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 74412 KB Output is correct
2 Correct 1693 ms 148388 KB Output is correct
3 Correct 467 ms 74472 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 74672 KB Output is correct
2 Correct 2044 ms 148600 KB Output is correct
3 Correct 653 ms 74444 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 52532 KB Output is correct
2 Correct 3260 ms 246952 KB Output is correct
3 Correct 241 ms 31048 KB Output is correct