oj.uz

Submission #147715

# Submission time Handle Problem Language Result Execution time Memory
147715 2019-08-30T13:19:32 Z Ruxandra985 Sirni (COCI17_sirni) C++14
112 / 140
 5000 ms 566576 KB 
#include <cstdio>
#include <vector> /// CHIAR AVEAM NEVOE SA IAU EC PT CA NU AVEAM DELOC NERVI CA NU IMI IESE:):):):)
#include <algorithm>
#define DIM 100010
using namespace std;
int v[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,mch,j,x,y,tx,ty;
    long long sol=0;
    scanf ("%d",&n);
    for (i=1;i<=n;i++){
        scanf ("%d",&v[i]);
    }
    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];
    }
    mch=0;
    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));
        }
        for (j=2*v[i];j<=v[n];j+=v[i]){
            /// cea mai mica val mai mare decat j
            x = biggest[j];
            if (j/v[i] == v[x]/v[i]){ /// add muchie
                m[v[x] - j].push_back(make_pair(i,x));
            }
        }
    }
    for (i=1;i<=n;i++)
        tt[i] = -1;
    int pus = 0;
    for (i=0;i<10000000 && pus!=n-1 ; i++){
        for (j=0;j<m[i].size();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:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=0;j<m[i].size();j++){
                  ~^~~~~~~~~~~~
sirni.cpp:29:20: warning: variable 'mch' set but not used [-Wunused-but-set-variable]
     int n,i,elem,p,mch,j,x,y,tx,ty;
                    ^~~
sirni.cpp:31:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d",&n);
     ~~~~~~^~~~~~~~~
sirni.cpp:33: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

# Verdict Execution time Memory Grader output
1 Correct 284 ms 274556 KB Output is correct
2 Correct 351 ms 276472 KB Output is correct
3 Correct 284 ms 274488 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 235352 KB Output is correct
2 Correct 1057 ms 275008 KB Output is correct
3 Correct 269 ms 274476 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 274472 KB Output is correct
2 Correct 263 ms 274316 KB Output is correct
3 Correct 265 ms 274424 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 249196 KB Output is correct
2 Correct 489 ms 276088 KB Output is correct
3 Correct 386 ms 254488 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 240760 KB Output is correct
2 Correct 497 ms 261212 KB Output is correct
3 Correct 287 ms 247196 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 261176 KB Output is correct
2 Correct 526 ms 290692 KB Output is correct
3 Correct 351 ms 252700 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 239576 KB Output is correct
2 Correct 521 ms 285568 KB Output is correct
3 Correct 322 ms 252760 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 287084 KB Output is correct
2 Correct 3331 ms 482468 KB Output is correct
3 Correct 491 ms 289368 KB Output is correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 286960 KB Output is correct
2 Execution timed out 5105 ms 566576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 276636 KB Output is correct
2 Execution timed out 5054 ms 536340 KB Time limit exceeded
3 Halted 0 ms 0 KB -