oj.uz

답안 #147722

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
147722 2019-08-30T13:33:38 Z Ruxandra985 Sirni (COCI17_sirni) C++14
140 / 140
 2020 ms 368412 KB 
/// ma doare capul si vreau sa scap de problema asta chiar daca mi s a parut chiar draguta ma oftica:))
#include <cstdio>
#include <vector>
#include <algorithm>
#define DIM 100010
using namespace std;
int v[DIM];
int dont[DIM];
vector <pair <int,int> > m[10000000];
int tt[DIM];
int biggest[10000010];
int fth ( int x ){
    int aux;
    int init = x;
    while (tt[x]>=0){
        x = tt[x];
    }
    while (tt[init]>=0){
        aux = tt[init];
        tt[init] = x;
        init = aux;
    }

    return x;
}
int main()
{
  //  freopen ("a.in" , "r" , stdin);
  //  freopen ("a.out" , "w" , stdout);
    int n,i,elem,p,j,x,y,tx,ty;
    long long sol=0;
    scanf ("%d",&n);
    for (i=1;i<=n;i++){
        scanf ("%d",&v[i]);
        tt[i] = -1;
    }
    sort (v+1,v+n+1);
    elem = 0;
    for (i=1;i<=n;i++){
        if (i==1 || v[i]!=v[i-1])
            v[++elem] = v[i];
    }
    n = elem;
    p=n;
    for (i=v[n];i;i--){
        if (p && v[p] == i){
            biggest[i] = p;
            p--;
        }
        else biggest[i] = biggest[i+1];
    }
    for (i=1;i<=n;i++){
        if (i!=n && v[i+1]/v[i] == 1){
            m[v[i+1] - v[i]].push_back(make_pair(i,i+1));
        }
        if (!dont[i]){
            for (j=2*v[i];j<=v[n];j+=v[i]){
                /// cea mai mica val mai mare decat j
                x = biggest[j];
                if (v[x] == j)
                    dont[x] = 1; /// de ce ai mai duce muchii din x cand sunt ca alea din i
                if (v[x] - j == v[x] % v[i]){ /// add muchie
                    m[v[x] - j].push_back(make_pair(i,x));
                }
            }
        }
    }
    int pus = 0;
    for (i=0;i<10000000 && pus!=n-1 ; i++){
        for (j=0;j<m[i].size() && pus!=n-1;j++){
            x = m[i][j].first;
            y = m[i][j].second;
            tx = fth(x);
            ty = fth(y);
            if (tx!=ty){
                sol+=i;
                pus++;
                //printf ("%d ",m[i].first);
                if (tt[tx] < tt[ty]){
                    tt[tx]+=tt[ty];
                    tt[ty] = tx;
                }
                else {
                    tt[ty]+=tt[tx];
                    tt[tx] = ty;
                }
            }
        }
    }
    printf ("%lld",sol);
    return 0;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=0;j<m[i].size() && pus!=n-1;j++){
                  ~^~~~~~~~~~~~
sirni.cpp:32:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d",&n);
     ~~~~~~^~~~~~~~~
sirni.cpp:34:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d",&v[i]);
         ~~~~~~^~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 274440 KB Output is correct
2 Correct 353 ms 276472 KB Output is correct
3 Correct 267 ms 274424 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 235228 KB Output is correct
2 Correct 430 ms 274516 KB Output is correct
3 Correct 269 ms 274664 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 268 ms 274484 KB Output is correct
2 Correct 264 ms 274300 KB Output is correct
3 Correct 266 ms 274424 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 247084 KB Output is correct
2 Correct 326 ms 253424 KB Output is correct
3 Correct 311 ms 252132 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 240888 KB Output is correct
2 Correct 348 ms 251604 KB Output is correct
3 Correct 276 ms 244696 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 331 ms 251924 KB Output is correct
2 Correct 339 ms 251892 KB Output is correct
3 Correct 287 ms 247140 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 238744 KB Output is correct
2 Correct 315 ms 251232 KB Output is correct
3 Correct 307 ms 249764 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 450 ms 286944 KB Output is correct
2 Correct 1153 ms 332764 KB Output is correct
3 Correct 493 ms 289256 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 499 ms 286140 KB Output is correct
2 Correct 1395 ms 342656 KB Output is correct
3 Correct 552 ms 293572 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 276692 KB Output is correct
2 Correct 2020 ms 368412 KB Output is correct
3 Correct 328 ms 251748 KB Output is correct