QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #65602 | #3045. Minimum Diameter Spanning Tree | gyh20 | AC ✓ | 166ms | 7696kb | C++14 | 1.6kb | 2022-12-02 11:19:35 | 2022-12-02 11:19:38 |
Judging History
answer
#include<bits/stdc++.h>
#define re register
#define int long long
using namespace std;
inline int read(){
re int t=0;re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return t;
}
int f[502][502],n,m,inf=1e18,g[502][502],p[502],X,ans,p1,p2,Usd[502],Dis;
inline bool cmp(re int x,re int y){return f[X][x]>f[X][y];}
signed main(){
n=read(),m=read(),ans=1e18;
for(re int i=1;i<=n;++i)for(re int j=1;j<=n;++j)f[i][j]=g[i][j]=inf;
for(re int i=1;i<=n;++i)f[i][i]=g[i][i]=0;
for(re int i=1;i<=m;++i){
re int x=read(),y=read(),z=read()*2;
f[x][y]=f[y][x]=g[x][y]=g[y][x]=z;
}
for(re int k=1;k<=n;++k)for(re int i=1;i<=n;++i)for(re int j=1;j<=n;++j)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
for(re int i=1;i<=n;++i){
for(re int j=1;j<=n;++j)p[j]=j;
X=i,sort(p+1,p+n+1,cmp);
if((f[i][p[1]]<<1)<ans)p1=p2=i,Dis=0,ans=min(ans,f[i][p[1]]<<1);
for(re int j=i+1;j<=n;++j){
for(re int k=2,pos=1;k<=n;++k)
if(f[j][p[k]]>f[j][p[pos]]){
if(f[i][p[k]]+f[j][p[pos]]+g[i][j]<ans)ans=min(ans,f[i][p[k]]+f[j][p[pos]]+g[i][j]),p1=i,p2=j,Dis=(f[i][p[k]]+f[j][p[pos]]+g[i][j])/2-f[i][p[k]];
pos=k;
}
}
}
printf("%lld\n",ans>>1),Usd[p1]=Usd[p2]=1;if(p1!=p2)printf("%lld %lld\n",p1,p2);
for(re int i=1;i<=n;++i)
for(re int j=1;j<=n;++j)
if(i!=j&&!Usd[j]&&f[p1][i]+g[i][j]==f[p1][j]&&(f[p1][j]+Dis<=f[p2][j]+g[p1][p2]-Dis))
Usd[j]=1,printf("%lld %lld\n",i,j);
for(re int i=1;i<=n;++i)
for(re int j=1;j<=n;++j)
if(i!=j&&!Usd[j]&&(f[p2][i]+g[i][j]==f[p2][j]))
Usd[j]=1,printf("%lld %lld\n",i,j);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3696kb
input:
3 3 1 2 1 2 3 1 3 1 1
output:
2 1 2 1 3
result:
ok
Test #2:
score: 0
Accepted
time: 2ms
memory: 3556kb
input:
6 7 1 2 10 2 3 20 1 3 30 3 4 1000 4 5 30 5 6 20 4 6 10
output:
1060 3 4 2 1 3 2 4 5 4 6
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
16 120 11 4 2 3 10 2 12 4 1 16 9 3 2 7 4 16 3 1 3 2 2 13 15 2 9 1 1 13 1 2 14 15 2 16 8 1 1 15 2 5 1 3 7 4 3 8 13 1 4 13 2 9 4 1 1 3 3 13 6 2 13 2 1 3 9 4 7 6 1 10 14 1 3 14 3 12 5 2 15 16 2 2 5 2 15 11 4 10 8 2 2 14 3 10 16 1 11 1 2 5 10 4 14 11 2 6 4 2 13 10 3 14 1 2 1 4 2 5 7 2 12 6 1 13 11 2 6 5...
output:
7 1 2 1 7 1 8 1 9 1 10 1 14 1 15 1 16 2 3 2 4 2 5 2 6 2 11 2 12 2 13
result:
ok
Test #4:
score: 0
Accepted
time: 24ms
memory: 5552kb
input:
256 32640 142 82 7 78 125 3 66 149 6 31 236 2 226 136 3 167 225 3 120 135 5 124 79 3 138 17 5 1 90 1 128 38 4 44 190 3 38 43 6 46 12 6 32 232 4 137 7 2 58 139 3 40 13 5 29 181 5 184 205 1 171 186 4 135 237 5 173 163 3 98 4 2 248 97 5 99 93 4 139 247 5 205 144 5 38 194 5 108 144 4 222 67 5 104 77 5 2...
output:
15 1 2 1 3 1 6 1 7 1 9 1 10 1 11 1 12 1 13 1 14 1 16 1 17 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 27 1 28 1 29 1 30 1 31 1 32 1 34 1 35 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 45 1 46 1 47 1 48 1 49 1 51 1 52 1 53 1 54 1 57 1 58 1 59 1 60 1 62 1 63 1 66 1 67 1 68 1 69 1 70 1 72 1 74 1 76 1 77 1 78 1 79 1 ...
result:
ok
Test #5:
score: 0
Accepted
time: 6ms
memory: 4516kb
input:
125 7750 17 50 7 72 112 7 92 14 4 18 99 5 115 55 9 96 10 5 98 16 4 116 76 9 58 28 8 37 80 4 10 102 3 20 92 7 12 104 5 92 106 7 109 48 6 125 56 6 20 47 3 40 80 6 67 32 2 37 21 7 48 117 6 33 41 7 93 10 3 13 114 6 68 25 1 109 94 2 36 118 6 58 3 7 40 104 6 40 76 1 118 91 7 55 93 2 44 48 2 27 99 8 79 10 ...
output:
12 14 89 1 43 1 63 1 96 2 6 2 11 2 15 2 24 2 27 2 51 2 55 2 59 2 90 2 95 2 105 8 40 8 76 10 7 10 28 10 35 10 70 10 116 12 1 12 8 12 16 12 30 12 31 12 33 12 36 12 38 12 42 12 44 12 45 12 50 12 57 12 65 12 84 12 91 12 98 12 101 12 108 12 110 12 111 12 114 12 115 12 124 13 92 14 2 14 10 14 12 14 13 14 ...
result:
ok
Test #6:
score: 0
Accepted
time: 44ms
memory: 6240kb
input:
343 58653 54 265 9 188 61 10 120 35 7 35 12 9 315 68 3 188 334 7 22 2 7 138 28 9 194 314 9 39 87 8 162 291 2 224 79 7 271 331 6 271 38 2 260 343 14 41 204 1 48 295 2 53 195 9 322 332 10 53 38 4 9 257 9 293 119 7 281 149 10 209 177 10 290 57 6 127 124 6 317 201 3 215 109 6 182 195 3 75 276 8 168 92 7...
output:
18 12 313 1 16 1 93 1 104 1 149 1 282 1 285 1 303 1 324 3 85 3 166 3 186 3 189 3 208 3 221 3 232 3 266 3 269 3 275 3 290 3 294 3 301 4 56 4 72 4 81 4 167 4 184 4 217 4 226 4 237 4 243 4 271 4 338 11 98 11 106 11 117 11 151 11 153 11 158 11 173 11 215 11 238 11 257 11 291 12 1 12 3 12 4 12 11 12 13 1...
result:
ok
Test #7:
score: 0
Accepted
time: 155ms
memory: 7696kb
input:
500 124750 443 468 569963 305 222 835365 55 98 5648875 17 483 6871804 249 387 957143 262 188 5962213 276 44 1213886 113 429 5230975 25 336 3434848 489 27 8708218 446 126 6079086 430 164 4406225 12 85 4614009 153 346 633874 316 368 5101625 236 369 2292881 387 66 5274904 220 278 3980069 146 303 544564...
output:
9960452 1 7 1 5 1 14 1 15 1 18 1 20 1 27 1 28 1 33 1 35 1 36 1 39 1 44 1 48 1 57 1 66 1 68 1 71 1 73 1 97 1 103 1 108 1 112 1 113 1 114 1 115 1 129 1 130 1 134 1 139 1 147 1 156 1 157 1 159 1 161 1 170 1 172 1 173 1 174 1 179 1 182 1 183 1 185 1 192 1 198 1 200 1 201 1 206 1 213 1 222 1 223 1 228 1 ...
result:
ok
Test #8:
score: 0
Accepted
time: 22ms
memory: 5708kb
input:
256 32640 67 46 8826982 212 207 5853106 75 245 11953237 34 125 17259394 17 120 10969533 155 3 6675664 141 92 13332413 244 88 7639683 137 79 3970040 73 176 19125293 169 201 4299143 73 163 12142015 14 6 12113321 75 256 9291130 63 157 12832584 228 29 6772645 68 175 13691783 5 89 4302943 16 103 6727852 ...
output:
26131854 138 155 1 36 1 52 1 90 1 115 1 162 1 184 1 186 6 7 6 28 6 33 6 44 6 63 6 64 6 83 6 112 6 120 6 139 6 170 6 230 6 249 22 41 22 76 22 94 22 131 22 150 35 62 35 140 35 142 35 166 35 207 35 209 35 246 58 11 58 84 58 93 58 196 58 226 58 238 58 252 75 1 75 22 75 35 75 123 75 126 75 179 95 58 95 7...
result:
ok
Test #9:
score: 0
Accepted
time: 24ms
memory: 5440kb
input:
243 29403 29 23 3131302 11 3 4511503 12 185 16507040 115 35 13690920 31 170 6850162 116 51 4745664 144 112 14201854 39 63 10109135 120 78 11204668 183 78 7290363 40 107 16689635 67 136 93441 67 55 15947263 39 143 4693652 154 107 10604580 127 183 10496797 208 122 13041508 11 26 6647372 126 229 985041...
output:
21457553 120 148 1 68 1 69 1 75 1 101 1 168 1 180 1 185 1 197 3 5 3 8 3 16 3 25 3 33 3 37 3 38 3 61 3 71 3 80 3 92 3 95 3 114 3 116 3 137 3 163 3 172 3 179 3 184 3 195 3 204 3 207 3 241 4 7 4 35 6 1 6 14 6 18 6 31 6 39 6 41 6 43 6 45 6 49 6 50 6 51 6 64 6 70 6 74 6 84 6 85 6 104 6 117 6 123 6 126 6 ...
result:
ok
Test #10:
score: 0
Accepted
time: 140ms
memory: 7688kb
input:
499 124251 461 265 336966683 376 414 284212683 366 413 337970820 9 149 355258271 325 156 315832696 113 375 354577875 32 433 345627841 376 161 335785529 366 42 319451479 385 172 321004557 98 236 360767420 444 326 313089369 36 115 337424941 392 238 340807288 85 347 336353275 116 372 371769911 391 13 3...
output:
733198522 198 406 406 1 406 2 406 3 406 4 406 5 406 6 406 7 406 8 406 9 406 10 406 11 406 12 406 13 406 14 406 15 406 16 406 17 406 18 406 19 406 20 406 21 406 22 406 23 406 24 406 25 406 26 406 27 406 28 406 29 406 30 406 31 406 32 406 33 406 34 406 35 406 36 406 37 406 38 406 39 406 40 406 41 406 ...
result:
ok
Test #11:
score: 0
Accepted
time: 147ms
memory: 7692kb
input:
500 124750 493 130 351043307 208 348 326179963 83 94 342055956 163 348 373258823 197 409 325293509 261 88 324333155 23 100 321384496 344 479 358400743 260 100 342652394 448 3 317675245 283 349 361779182 414 197 327194724 37 459 389772936 401 126 344352426 60 46 312990080 313 242 318912361 198 98 325...
output:
738068891 266 448 266 1 266 2 266 3 266 4 266 5 266 6 266 7 266 8 266 9 266 10 266 11 266 12 266 13 266 14 266 15 266 16 266 17 266 18 266 19 266 20 266 21 266 22 266 23 266 24 266 25 266 26 266 27 266 28 266 29 266 30 266 31 266 32 266 33 266 34 266 35 266 36 266 37 266 38 266 39 266 40 266 41 266 ...
result:
ok
Test #12:
score: 0
Accepted
time: 153ms
memory: 7540kb
input:
500 124750 263 149 823 1 65 751 53 409 870 292 352 762 379 122 767 484 74 812 115 497 832 297 334 823 210 41 809 420 268 807 95 216 752 186 423 791 427 358 776 118 223 775 459 211 808 162 343 751 210 119 809 439 195 844 154 221 822 363 390 822 339 270 807 153 15 837 426 330 773 354 315 762 317 303 7...
output:
1687 137 487 487 1 487 2 487 3 487 4 487 5 487 6 487 7 487 8 487 9 487 10 487 11 487 12 487 13 487 14 487 15 487 16 487 17 487 18 487 19 487 20 487 21 487 22 487 23 487 24 487 25 487 26 487 27 487 28 487 29 487 30 487 31 487 32 487 33 487 34 487 35 487 36 487 37 487 38 487 39 487 40 487 41 487 42 48...
result:
ok
Test #13:
score: 0
Accepted
time: 154ms
memory: 7420kb
input:
500 124750 24 277 336609231 189 48 329957751 130 307 334562839 150 5 350299699 130 306 338627627 391 416 326018518 297 489 326045958 156 153 333330346 154 482 339034861 492 259 323077166 370 5 333649013 258 204 324978731 64 228 352908115 58 244 340587477 429 419 321475204 151 143 325381408 248 38 33...
output:
695755972 3 359 359 1 359 2 359 4 359 5 359 6 359 7 359 8 359 9 359 10 359 11 359 12 359 13 359 14 359 15 359 16 359 17 359 18 359 19 359 20 359 21 359 22 359 23 359 24 359 25 359 26 359 27 359 28 359 29 359 30 359 31 359 32 359 33 359 34 359 35 359 36 359 37 359 38 359 39 359 40 359 41 359 42 359 4...
result:
ok
Test #14:
score: 0
Accepted
time: 150ms
memory: 7452kb
input:
500 124750 384 14 425038468 192 260 675657326 292 198 23251605 1 463 124292609 231 2 178513186 300 408 50265695 320 78 81387545 90 190 923582754 498 409 916628446 420 166 299413262 23 339 542251129 5 237 493710510 251 6 12885827 444 8 440135613 242 173 686046528 30 301 61808439 264 60 642406301 248 ...
output:
40740713 204 246 14 209 21 78 21 84 21 145 21 265 21 274 21 299 21 322 21 374 35 199 37 68 37 86 37 149 37 189 37 207 37 395 37 432 38 40 38 171 38 439 40 118 42 212 45 354 47 371 63 361 65 219 68 352 68 480 81 391 82 45 82 126 84 434 86 106 86 270 86 362 90 369 97 406 102 290 104 313 109 132 109 32...
result:
ok
Test #15:
score: 0
Accepted
time: 145ms
memory: 7496kb
input:
500 124750 202 447 336741012 92 270 663436926 89 41 309047741 345 240 587182923 14 358 303518613 107 72 624877592 270 468 280136986 256 150 719953302 451 155 767165840 99 256 496809180 24 72 326743318 199 127 228787790 326 143 349499492 326 358 965377787 7 404 903718497 52 100 838914124 219 233 6663...
output:
46749755 132 408 12 86 28 363 48 59 59 75 59 320 59 351 132 48 132 112 132 322 132 324 132 371 132 373 132 374 206 12 206 28 206 356 322 23 322 73 322 257 322 405 324 24 324 113 324 206 324 385 324 391 324 399 364 106 364 263 405 209 405 364 1 212 1 255 2 13 3 496 7 150 7 261 7 492 13 200 15 89 16 3...
result:
ok
Test #16:
score: 0
Accepted
time: 144ms
memory: 7440kb
input:
500 124750 473 261 267443376 438 59 540452305 197 481 350240182 99 51 255230904 235 459 810428481 153 287 364214007 316 333 252023630 141 84 602938702 390 38 840115034 80 121 768116227 188 336 316269065 246 63 532812842 159 9 600703944 39 5 983000839 342 140 197843308 377 410 592004365 15 135 203770...
output:
37971004 137 192 1 270 1 388 4 79 4 132 9 294 10 421 15 100 15 138 15 259 15 263 16 459 16 494 17 116 17 307 17 354 22 201 22 454 23 228 23 302 23 332 23 360 26 121 26 162 26 231 32 280 32 399 35 202 35 221 35 229 35 247 35 273 46 32 47 418 50 87 53 15 53 60 53 188 53 227 53 477 57 352 58 82 58 245 ...
result:
ok
Test #17:
score: 0
Accepted
time: 146ms
memory: 7444kb
input:
500 124750 326 216 865974032 342 145 899173929 326 17 95028303 270 362 420387995 495 164 932329585 69 201 348342984 189 89 860429924 171 314 195039912 302 399 8710790 495 328 336795245 227 164 322999677 49 444 746557 349 7 208544655 134 150 54925387 305 347 75313895 367 143 447473444 485 95 28555430...
output:
41635892 226 291 7 184 15 359 28 159 28 192 29 231 30 143 31 34 31 103 36 234 36 305 41 239 47 247 65 343 71 317 73 43 73 111 73 262 74 183 74 265 74 427 74 448 80 346 80 416 82 87 82 200 83 109 86 65 86 335 86 363 98 56 106 313 106 455 107 266 116 181 121 142 133 41 133 168 133 483 136 92 136 492 1...
result:
ok
Test #18:
score: 0
Accepted
time: 133ms
memory: 7420kb
input:
500 124750 50 103 169644033 350 25 733427517 360 329 325740461 491 358 863234848 246 109 425224534 3 106 362191273 495 24 283250521 375 458 893528294 364 423 711146313 150 15 835762784 150 331 623176965 405 70 386196999 65 177 211037895 445 279 242692580 340 109 410272265 173 268 334368275 263 447 7...
output:
42973111 1 192 1 108 1 187 1 198 1 249 1 277 1 462 8 240 20 68 20 225 20 303 20 392 24 419 34 294 56 224 57 51 57 315 59 24 78 79 78 131 78 230 78 296 79 34 79 497 93 15 93 346 101 155 103 160 108 174 108 257 108 279 108 473 112 262 113 47 120 375 120 500 128 361 131 275 143 348 143 380 152 338 156 ...
result:
ok
Test #19:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
10 45 1 8 852386547 1 6 896725964 1 7 398330288 10 7 745956332 4 3 77447028 7 9 397520615 8 6 802361809 4 7 772673968 1 2 174055957 10 5 103665853 4 9 485247227 4 2 258249623 9 2 728388812 7 8 106246975 8 10 888960723 8 2 598923263 7 6 905994898 4 5 576321126 3 8 770589879 10 1 496876256 1 5 8349896...
output:
423806871 5 7 3 2 3 4 5 9 5 10 9 1 9 3 9 6 7 8
result:
ok
Test #20:
score: 0
Accepted
time: 2ms
memory: 3844kb
input:
10 45 2 8 114030772 9 6 370138763 4 1 649979236 9 10 595837331 1 3 398896234 3 4 916893101 7 2 927242800 9 8 85375078 6 4 628048978 10 1 62710986 10 8 198495177 2 9 620688683 3 2 817822965 1 7 475778205 2 6 444985984 7 4 791328882 5 10 714881954 2 4 92374685 9 3 509479385 7 5 472012838 8 6 515456030...
output:
588353283 8 10 2 4 8 2 8 9 3 5 6 7 7 3 10 1 10 6
result:
ok
Test #21:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
10 45 3 2 411603519 2 1 530222805 5 8 401884056 2 8 629138281 9 4 279043576 2 7 355714714 9 1 16302019 2 4 366691234 3 6 641321323 9 2 102923145 5 10 471322247 9 3 276998611 4 5 140929491 10 3 625579125 1 4 525865610 6 7 200122395 7 8 412320889 10 7 215063702 1 6 950279547 5 9 122526015 10 2 4510894...
output:
668030625 8 10 5 4 8 9 9 1 9 2 9 3 9 5 9 6 9 7
result:
ok
Test #22:
score: 0
Accepted
time: 135ms
memory: 7420kb
input:
500 499 489 250 911816417 42 183 576360685 413 27 603166565 340 6 740155781 282 267 886335166 202 36 846414216 70 273 536335885 94 400 679118131 186 292 325240258 68 99 356682437 93 324 130056528 202 490 975232337 374 459 608441376 3 217 840906454 40 367 175667143 306 120 471709580 120 215 691146618...
output:
32760257077 211 378 1 140 1 322 3 217 3 441 4 133 6 74 11 45 13 256 14 467 15 198 15 263 16 78 16 196 16 330 20 447 21 155 23 406 25 335 32 161 34 135 35 307 37 62 41 240 41 382 45 126 46 107 49 235 52 279 52 318 55 1 55 41 59 221 59 290 59 410 60 455 61 303 61 389 64 236 64 315 67 11 68 76 68 99 68...
result:
ok
Test #23:
score: 0
Accepted
time: 164ms
memory: 7436kb
input:
499 498 115 438 632124054 265 323 590854058 205 408 640558868 144 190 863488857 496 129 397594428 70 111 349959309 263 29 495455138 401 358 394611413 489 425 957892531 142 332 389151686 133 38 15576349 228 379 52447487 320 283 49471342 437 390 652438631 51 37 41057275 473 6 599793848 313 450 3796515...
output:
33794638693 63 279 3 31 3 263 29 482 31 491 41 389 48 241 63 275 63 332 66 73 66 183 71 77 73 145 76 247 76 423 83 7 83 220 84 306 99 266 138 173 138 361 139 434 139 465 142 99 142 228 142 305 142 386 144 190 145 356 152 209 152 388 164 471 166 160 173 420 173 478 177 71 196 373 207 89 207 138 207 2...
result:
ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
3 2 2 3 255741785 2 1 160496570
output:
416238355 2 3 2 1
result:
ok
Test #25:
score: 0
Accepted
time: 3ms
memory: 4412kb
input:
100 99 65 34 441414148 22 95 527003384 74 85 80656954 10 64 893508913 32 42 110880114 91 74 519216315 68 70 233703686 20 92 370689334 39 48 209550382 52 1 846701392 94 10 214278326 84 99 574671008 21 43 936333553 92 75 889270962 55 69 989214957 67 83 121514850 21 87 989248231 2 26 935422061 80 65 95...
output:
14316191893 43 80 1 90 2 26 2 31 2 32 2 44 6 58 7 25 7 96 11 45 11 50 16 61 17 38 17 100 20 97 21 51 21 55 21 87 25 29 25 52 25 67 26 8 29 23 31 71 31 91 32 42 32 66 33 68 40 6 40 16 43 21 45 13 45 82 49 63 51 92 52 1 53 93 55 69 55 76 63 40 66 98 67 11 67 17 67 83 68 2 68 59 68 60 68 70 74 85 75 5 ...
result:
ok
Test #26:
score: 0
Accepted
time: 131ms
memory: 7540kb
input:
500 499 84 429 1000000000 221 147 1000000000 32 342 1000000000 215 314 1000000000 119 179 1000000000 108 435 1000000000 387 152 1000000000 205 212 1000000000 269 394 1000000000 275 474 1000000000 448 350 1000000000 359 365 1000000000 296 402 1000000000 224 73 1000000000 109 499 1000000000 349 351 10...
output:
499000000000 401 428 3 293 5 329 6 436 11 113 13 202 14 442 15 316 16 486 17 20 19 90 20 370 24 434 26 189 31 145 32 342 33 233 34 15 35 85 37 126 38 183 40 24 45 185 46 230 47 384 48 69 51 54 53 262 54 258 57 391 58 38 59 336 63 278 64 343 66 161 67 66 68 483 69 208 71 356 72 110 73 224 74 279 75 2...
result:
ok
Test #27:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
2 1 1 2 1000000000
output:
1000000000 1 2
result:
ok
Test #28:
score: 0
Accepted
time: 166ms
memory: 7420kb
input:
500 112375 215 411 405573103 483 202 429632204 49 152 641147973 424 223 313115211 102 480 37625732 135 498 287528728 11 372 755681501 60 331 159823988 227 78 518118983 185 167 755911454 130 269 191205737 55 152 445920241 152 407 834003692 113 185 512296966 396 177 680449942 371 473 23006247 125 47 6...
output:
46093603 18 162 8 421 18 61 18 258 18 267 18 334 18 357 23 487 32 90 32 146 32 295 32 298 32 324 61 328 96 23 96 151 96 479 105 8 105 494 185 72 209 47 258 216 258 390 267 69 267 409 293 209 306 180 328 462 334 39 334 96 334 200 334 391 347 293 357 32 357 98 357 306 391 186 391 219 391 419 419 347 4...
result:
ok
Test #29:
score: 0
Accepted
time: 132ms
memory: 7608kb
input:
500 62254 428 55 673055918 215 410 148588730 75 376 213490326 263 232 596161560 64 398 839662234 170 473 426273328 221 214 725162854 8 382 656895268 407 251 472418635 285 64 454705591 238 432 602541117 340 392 788352611 68 108 508348843 328 297 694088955 25 51 861300749 255 242 119135283 270 496 758...
output:
93031648 209 256 3 439 9 93 9 114 13 355 18 223 18 448 19 151 21 29 21 124 21 368 21 436 22 319 22 415 24 497 29 228 29 341 29 359 31 160 31 197 31 329 31 374 31 386 33 14 33 231 33 286 35 3 36 230 36 340 38 220 42 18 43 453 45 262 47 87 48 493 49 445 51 28 51 188 53 396 53 431 56 65 56 116 56 269 5...
result:
ok
Test #30:
score: 0
Accepted
time: 137ms
memory: 7420kb
input:
500 24926 202 335 87826903 145 367 249043133 296 266 234995839 400 252 908643196 247 365 670330835 365 312 417431159 400 490 824592807 403 123 901931953 226 363 926551074 453 488 215017578 144 225 960418940 205 69 506382361 489 133 278874199 468 146 198386148 222 216 496678072 349 342 300581775 158 ...
output:
195696372 35 144 19 365 22 53 22 164 29 201 35 99 35 105 35 119 35 277 35 311 35 343 35 346 35 437 37 208 39 81 39 268 39 286 41 37 41 260 43 472 53 441 54 175 54 207 54 220 54 257 55 93 55 233 56 429 56 500 63 86 66 50 68 296 72 234 78 344 80 167 80 323 81 65 84 241 84 263 86 54 86 173 86 400 91 69...
result:
ok
Test #31:
score: 0
Accepted
time: 132ms
memory: 7464kb
input:
500 7425 81 342 810238489 27 14 908239231 273 373 287258613 253 432 563166711 278 199 932063977 373 100 814478323 426 105 374600399 60 251 16098593 166 201 655716982 456 168 66673197 30 121 595035829 170 431 817407488 173 126 660336891 226 220 24714054 386 278 322211588 16 12 54069814 406 341 169888...
output:
635007062 314 392 1 492 12 473 16 12 16 239 19 216 22 194 22 426 25 96 25 169 26 124 26 283 26 389 38 16 46 413 56 332 60 251 66 146 67 475 78 134 78 217 79 182 79 249 79 340 79 423 81 334 90 43 90 494 96 72 96 368 98 67 99 366 101 1 115 281 117 271 123 139 123 266 123 417 127 500 139 166 139 175 13...
result:
ok
Test #32:
score: 0
Accepted
time: 135ms
memory: 7496kb
input:
500 3780 366 95 394951594 6 366 802428678 87 202 504216135 478 261 621604711 108 261 136061971 119 31 234424551 265 405 267843581 403 307 789242971 80 208 9360049 23 151 536803184 35 208 113064121 17 442 868266027 419 438 844536791 32 31 683803313 420 211 824670471 13 227 45871642 312 124 865431657 ...
output:
1442276057 69 97 69 285 69 340 69 456 74 134 134 390 134 401 134 440 285 166 285 290 300 107 344 126 440 112 456 74 456 300 456 344 3 71 3 252 3 305 3 457 4 281 5 438 6 203 6 223 6 267 8 1 8 242 11 238 13 181 13 243 13 482 14 253 15 192 16 77 22 152 22 426 23 106 23 367 23 409 23 493 24 339 26 56 26...
result:
ok
Test #33:
score: 0
Accepted
time: 135ms
memory: 7624kb
input:
499 7413 453 253 365177445 73 82 676484140 472 167 572434873 292 454 881725762 351 448 816134721 11 74 99817392 3 152 899527423 343 267 283437304 317 368 658958165 302 12 545721809 25 252 826963352 238 102 653491178 49 405 499572039 7 95 632608197 337 427 400888272 291 307 41716753 97 222 154670567 ...
output:
649053601 17 109 4 62 6 7 17 59 17 350 17 374 17 485 23 232 23 483 27 158 27 309 29 303 37 453 37 495 40 43 40 221 40 272 40 402 43 96 48 361 49 80 49 197 50 152 53 497 55 89 55 160 55 210 55 273 55 407 55 425 55 441 59 55 59 75 59 113 59 153 59 229 59 245 59 292 61 490 63 142 63 242 63 364 71 32 72...
result:
ok
Test #34:
score: 0
Accepted
time: 139ms
memory: 7420kb
input:
500 998 357 37 615878375 355 220 158580531 459 81 359502925 464 212 517883144 423 87 670629712 144 226 399414281 138 360 72111835 317 390 728659672 445 53 690042117 451 15 711431052 279 52 747492925 292 177 846356995 468 170 50253940 282 237 706952552 336 337 720468410 259 156 356422088 170 428 7889...
output:
4441235878 247 443 1 140 1 322 1 486 2 54 2 169 2 223 2 471 3 441 6 74 6 340 13 256 17 371 17 389 23 43 23 290 23 406 23 408 26 106 26 450 30 158 30 327 32 45 32 333 35 91 35 307 37 62 37 174 37 357 38 115 38 159 41 382 43 302 44 284 50 432 52 279 52 318 53 8 54 17 54 18 54 201 54 456 55 1 55 41 55 ...
result:
ok
Test #35:
score: 0
Accepted
time: 139ms
memory: 7448kb
input:
500 1489 251 283 336346626 268 345 197720766 140 346 368809904 481 154 810739392 283 82 466080515 316 88 398780699 337 220 873542149 220 300 789681082 495 292 836172158 122 274 642176095 310 404 583796616 78 397 116645447 112 95 526153997 252 242 538439401 199 155 108445198 221 142 170150171 14 123 ...
output:
3335034921 294 392 2 441 4 158 9 121 9 497 10 194 16 330 16 357 16 384 21 155 21 173 21 489 26 86 26 450 30 311 31 129 31 222 31 263 32 333 32 461 35 91 36 291 36 448 41 351 42 183 46 390 49 21 49 104 49 211 49 332 50 432 51 116 52 366 53 8 61 372 61 380 61 389 62 107 64 200 64 496 66 164 68 403 72 ...
result:
ok
Test #36:
score: 0
Accepted
time: 138ms
memory: 7420kb
input:
500 1983 390 46 325419612 352 173 956124303 21 49 87118967 434 293 181309943 1 322 966816097 374 363 405786700 387 462 663285952 221 431 114079525 386 364 919848935 364 377 588992539 64 111 763731869 239 380 467883942 37 62 914591429 299 194 812634844 41 352 774415821 166 259 622646113 439 393 67889...
output:
2538508929 91 284 9 121 9 498 11 45 11 451 13 256 16 357 22 5 22 314 22 423 23 408 25 299 25 335 25 379 26 86 29 72 30 311 30 327 31 129 32 333 33 9 33 12 33 371 33 477 34 180 35 22 35 98 35 111 35 144 35 166 35 239 35 307 36 291 36 448 38 115 38 250 38 275 39 1 41 114 41 240 41 351 41 492 42 183 48...
result:
ok
Test #37:
score: 0
Accepted
time: 134ms
memory: 7472kb
input:
500 2472 26 259 300350996 483 172 113333131 223 2 360381923 291 42 637617104 350 300 449910518 26 163 611186507 472 365 189750058 343 110 448614498 28 77 642365375 65 5 815239874 76 259 900880611 371 17 711438797 489 79 89712650 476 225 198266248 277 357 648844147 29 235 887755827 343 90 437780951 1...
output:
1987249621 35 91 1 39 4 138 16 357 22 5 22 314 22 356 32 333 32 366 33 12 33 62 35 22 35 64 35 98 35 144 35 166 35 239 35 307 38 115 38 150 38 250 38 275 41 114 41 351 47 457 50 156 50 303 50 432 53 8 58 165 58 228 58 353 64 255 64 315 64 496 65 162 66 84 66 371 69 133 69 175 69 236 76 342 76 384 78...
result:
ok
Test #38:
score: 0
Accepted
time: 137ms
memory: 7420kb
input:
500 2957 465 121 968799590 205 395 23464769 131 186 292946801 138 399 632201011 404 23 254378437 13 40 610881364 389 61 43222378 118 164 621828299 380 310 876201865 393 260 582208954 360 43 303515652 278 449 587854697 204 107 450595359 312 165 693035862 239 311 426200604 368 347 875502366 456 215 23...
output:
1720003538 285 417 1 39 6 76 6 110 6 191 6 427 9 75 9 193 9 491 9 498 11 451 13 72 21 381 22 92 22 350 24 399 24 421 25 368 25 379 26 86 26 256 26 450 27 361 31 44 31 257 31 483 32 360 33 12 33 62 34 334 34 343 35 64 35 98 35 144 35 166 35 307 36 291 36 298 36 473 38 150 38 177 38 187 38 250 38 275 ...
result:
ok
Test #39:
score: 0
Accepted
time: 139ms
memory: 7460kb
input:
500 3445 260 191 387557630 460 96 437785661 414 157 788571963 467 204 422896812 275 38 82565240 154 319 186508009 400 94 679118131 347 180 401381454 98 147 462666191 112 84 164496728 122 77 698092305 217 295 71771915 430 403 650087807 156 396 553244458 357 16 110311943 467 130 833512070 38 352 62662...
output:
1483608654 379 454 4 158 4 305 7 186 9 235 9 498 13 256 14 487 16 101 16 357 18 405 19 147 21 381 24 112 24 399 25 76 25 299 25 317 25 335 25 368 27 458 30 224 30 311 30 319 30 341 31 373 32 360 36 291 36 473 38 275 40 367 40 444 40 500 41 54 41 114 41 351 41 382 42 132 47 457 49 21 49 67 49 110 49 ...
result:
ok
Test #40:
score: 0
Accepted
time: 2ms
memory: 3808kb
input:
17 30 16 4 554374432 9 2 215208399 5 3 513409742 6 14 506215306 7 13 537124830 16 15 143014337 17 10 816248153 1 7 242153020 6 2 37119022 12 8 137831502 16 11 237336357 9 1 881761968 14 12 318095050 8 1 208032501 6 10 190870607 15 14 346948152 13 3 846045895 3 11 694053968 14 17 419599539 6 5 208704...
output:
1817998100 1 3 1 7 1 8 2 6 2 9 6 10 8 12 12 2 3 4 3 5 3 13 3 17 11 16 16 15 17 11 17 14
result:
ok
Test #41:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
17 43 4 3 506147731 2 6 37119022 3 5 513409742 6 12 516377635 4 15 675716898 17 11 219922878 7 1 242153020 13 4 133275785 16 3 940198937 8 4 956435856 4 16 554374432 17 14 419599539 14 16 933384890 14 4 298309896 2 12 8225926 5 2 713365483 14 12 318095050 12 8 225374527 17 3 189766466 7 13 537124830...
output:
1381676961 12 14 2 6 2 9 6 10 8 1 9 7 12 2 12 8 4 13 14 4 14 5 14 15 15 16 15 17 17 3 17 11
result:
ok
Test #42:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
17 56 15 12 174616807 14 12 318095050 4 8 956435856 8 1 208032501 6 14 506215306 7 9 112445395 3 16 940198937 9 1 881761968 15 16 143014337 17 10 816248153 5 3 513409742 13 5 110880114 12 8 225374527 2 16 286986530 14 16 441504628 7 1 242153020 6 10 190870607 2 9 215208399 6 13 116383718 15 14 34694...
output:
793723258 12 15 2 6 2 9 6 4 6 5 6 10 6 13 9 7 12 1 12 2 12 8 12 14 15 16 15 17 17 3 17 11
result:
ok
Test #43:
score: 0
Accepted
time: 2ms
memory: 3892kb
input:
17 65 6 17 197550393 15 14 346948152 17 5 893508913 12 15 174616807 7 16 324584324 9 12 973708325 16 11 237336357 3 11 436207833 3 1 389872647 7 2 580944484 13 7 537124830 11 17 833923911 15 4 675716898 14 17 419599539 12 11 905778941 14 4 298309896 6 2 37119022 16 15 143014337 11 7 519216315 4 5 45...
output:
679248086 2 6 2 9 2 12 2 16 9 7 12 1 12 8 12 14 12 15 6 4 6 5 6 10 6 13 6 17 13 3 13 11
result:
ok
Test #44:
score: 0
Accepted
time: 2ms
memory: 3740kb
input:
10 44 7 1 517400951 10 3 471593384 1 3 547761444 7 8 791370537 4 5 369007550 2 5 564183890 3 9 965720849 2 6 130399919 6 4 756732023 9 8 902540844 6 9 760427451 10 5 162352859 3 2 908640945 10 8 531885690 10 2 113869678 9 5 196323620 5 1 460453279 1 10 660682369 1 2 359263377 8 5 112464084 6 8 17956...
output:
741272030 5 6 5 9 2 7 2 10 6 1 6 2 6 8 8 3 10 4
result:
ok
Test #45:
score: 0
Accepted
time: 145ms
memory: 7556kb
input:
500 124750 473 98 225 91 199 248 16 76 249 203 221 249 431 332 256 184 406 264 324 101 263 197 10 229 275 267 239 240 23 260 461 74 252 169 242 266 197 49 253 70 307 250 33 235 235 429 201 249 470 303 236 239 250 235 377 461 247 46 47 258 337 204 245 162 287 256 44 256 239 55 32 257 65 273 252 398 2...
output:
546 184 1 184 2 184 3 184 4 184 5 184 6 184 7 184 8 184 9 184 10 184 11 184 12 184 13 184 14 184 15 184 16 184 17 184 18 184 19 184 20 184 21 184 22 184 23 184 24 184 25 184 26 184 27 184 28 184 29 184 30 184 31 184 32 184 33 184 34 184 35 184 36 184 37 184 38 184 39 184 40 184 41 184 42 184 43 184 ...
result:
ok
Test #46:
score: 0
Accepted
time: 139ms
memory: 7460kb
input:
500 124750 304 88 436 94 161 421 447 321 442 404 288 462 137 200 420 195 380 453 451 351 444 402 232 423 344 60 439 286 379 452 149 388 484 468 310 445 6 409 429 130 335 410 265 323 440 146 181 442 398 185 451 336 242 455 303 237 436 441 330 428 314 428 468 97 5 456 45 295 421 231 104 443 360 61 444...
output:
942 430 1 430 2 430 3 430 4 430 5 430 6 430 7 430 8 430 9 430 10 430 11 430 12 430 13 430 14 430 15 430 16 430 17 430 18 430 19 430 20 430 21 430 22 430 23 430 24 430 25 430 26 430 27 430 28 430 29 430 30 430 31 430 32 430 33 430 34 430 35 430 36 430 37 430 38 430 39 430 40 430 41 430 42 430 43 430 ...
result:
ok