# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
147715 | 2019-08-30T13:19:32 Z | Ruxandra985 | Sirni (COCI17_sirni) | C++14 | 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
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 | - |
# | 결과 | 실행 시간 | 메모리 | 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 | - |