oj.uz

답안 #152331

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152331 2019-09-07T15:07:42 Z alexandra_udristoiu Sirni (COCI17_sirni) C++14
98 / 140
 5000 ms 263852 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#define f first
#define s second
#define DIM 100005
using namespace std;
int n, i, j, r1, r2, p, u, mid;
long long sol;
int v[DIM], r[DIM];
vector< pair<int, int> > w;
int cmp(pair<int, int> a, pair<int, int> b){
    return v[a.f] % v[a.s] < v[b.f] % v[b.s];
}
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++){
        if(v[i + 1] < 2 * v[i]){
            w.push_back( make_pair(i + 1, i) );
        }
    }
    for(i = 1; i < n; i++){
        p = i + 1;
        for(j = v[i] + v[i]; j <= v[n]; j += v[i]){
            if(v[p] >= j + v[i]){
                continue;
            }
            u = n;
            while(p <= u){
                mid = (p + u) / 2;
                if(v[mid] >= j){
                    u = mid - 1;
                }
                else{
                    p = mid + 1;
                }
            }
            if(v[p] < j + v[i]){
                w.push_back( make_pair(p, 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 += v[ w[i].f ] % v[ w[i].s ];
            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:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 0; i < w.size(); i++){
                ~~^~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 74 ms 2540 KB Output is correct
3 Correct 7 ms 504 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 146 ms 1012 KB Output is correct
3 Correct 7 ms 504 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 6 ms 504 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 422 ms 9332 KB Output is correct
2 Correct 1470 ms 33892 KB Output is correct
3 Correct 580 ms 17476 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 2668 KB Output is correct
2 Correct 851 ms 33888 KB Output is correct
3 Correct 411 ms 9532 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 921 ms 33956 KB Output is correct
2 Correct 1896 ms 66712 KB Output is correct
3 Correct 536 ms 17488 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 4924 KB Output is correct
2 Correct 1815 ms 66860 KB Output is correct
3 Correct 513 ms 17372 KB Output is correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 557 ms 17568 KB Output is correct
2 Execution timed out 5080 ms 263824 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 542 ms 17452 KB Output is correct
2 Execution timed out 5098 ms 263852 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 2668 KB Output is correct
2 Execution timed out 5095 ms 263756 KB Time limit exceeded
3 Halted 0 ms 0 KB -