QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#750821 | #8235. Top Cluster | zhouyuxuan3501 | WA | 1225ms | 178824kb | C++14 | 1.7kb | 2024-11-15 16:03:21 | 2024-11-15 16:03:21 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#define L long long
using namespace std;
const int Mn=1e6+11;
struct I
{
int h,w;
bool operator<(const I& k)const
{
return w<k.w;
}
}k[Mn],D[Mn];
vector<I> c[Mn];
int n,Q,S[Mn],q[Mn][21],s,E[Mn],z;
L g[Mn];
void dfs(int l,int F)
{
S[l]=S[F]+1;
q[++s][0]=l;
E[l]=s;
for(auto h:c[l])
{
if(h.h==F)continue;
g[h.h]=g[l]+h.w;
dfs(h.h,l);
q[++s][0]=l;
}
}
int lca(int j,int h)
{
j=E[j];
h=E[h];
if(j>h)swap(j,h);
int p=log2(h-j+1),s1,s2;
s1=q[j][p];
s2=q[h-(1<<p)+1][p];
if(S[s1]<S[s2])return s1;
return s2;
}
L Gd(int j,int h)
{
int p=lca(j,h);
return g[j]+g[h]-g[p]-g[p];
}
int main()
{
int i,j,h,s1,s2,A,B;
L w,p;
scanf("%d%d",&n,&Q);
for(i=1;i<=n;i++)
{
k[i].h=i;
scanf("%d",&k[i].w);
}
sort(k+1,k+n+1);
for(i=1;i<n;i++)
{
scanf("%d%d%lld",&j,&h,&w);
c[j].push_back({h,w});
c[h].push_back({j,w});
}
dfs(1,0);
for(i=1;i<21;i++)
for(h=1;h+(1<<(i-1))<=s;h++)
{
s1=q[h][i-1];
s2=q[h+(1<<(i-1))][i-1];
q[h][i]=(S[s1]<S[s2])?s1:s2;
}
for(i=1;i<=n;i++)if(k[i].w!=i-1){z=i-1;break;}
D[1]={k[1].h,k[1].h};
for(i=2;i<=n;i++)
{
D[i]=D[i-1];
w=Gd(D[i].h,D[i].w);
p=Gd(D[i-1].h,k[i].h);
if(p>w)
{
w=p;
D[i]={D[i-1].h,k[i].h};
}
p=Gd(D[i-1].w,k[i].h);
if(p>w)
{
w=p;
D[i]={D[i-1].w,k[i].h};
};
}
while(Q--)
{
scanf("%d%lld",&i,&w);
A=1;B=n;h=n+1;
while(A<=B)
{
j=(A+B)>>1;
p=max(Gd(D[j].h,i),Gd(D[j].w,i));
if(p>w)
{
h=j;
B=j-1;
}
else A=j+1;
}
p=z;
if(h!=n+1)p=min(p,1LL*k[h].w);
printf("%d\n",p);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 34540kb
input:
5 4 3 9 0 1 2 1 2 10 3 1 4 3 4 3 3 5 2 3 0 1 0 4 6 4 7
output:
1 0 3 4
result:
ok 4 number(s): "1 0 3 4"
Test #2:
score: 0
Accepted
time: 1116ms
memory: 150604kb
input:
500000 500000 350828 420188 171646 209344 4 999941289 289054 79183 999948352 427544 160827 138994 192204 108365 99596 999987124 292578 2949 384841 269390 999920664 315611 163146 51795 265839 34188 999939494 145387 366234 86466 220368 357231 347706 332064 279036 173185 5901 217061 112848 37915 377359...
output:
0 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 2499...
result:
ok 500000 numbers
Test #3:
score: 0
Accepted
time: 1144ms
memory: 151824kb
input:
500000 500000 416779 59604 366180 195604 4 30957 999969109 7476 352690 368624 121597 999960303 999933891 13 14 138579 294015 227392 106760 117837 208506 999997971 34770 40258 182765 65889 206246 233051 130491 182099 117381 241945 449750 155921 356191 999955435 2243 450904 242106 178163 148523 75648 ...
output:
0 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 250002 2500...
result:
ok 500000 numbers
Test #4:
score: 0
Accepted
time: 1186ms
memory: 166640kb
input:
500000 500000 161260 258036 999901390 280191 21975 193647 397811 362276 206096 421117 336278 416815 31870 999934957 999977591 15 999991550 235871 999916756 19 241647 466194 218880 352702 84559 479034 24903 124981 339271 153019 157132 333035 124326 464181 219609 94164 999933701 440055 118732 2285 175...
output:
0 250000 250000 69 10 250000 250000 0 5 250000 250000 250000 1 33 69 10 250000 250000 250000 10 0 250000 250000 250000 1 250000 250000 0 250000 10 5 0 33 10 250000 1 66 250000 1 250000 1 250000 250000 250000 16 1 1 0 5 10 250000 250000 0 250000 250000 250000 250000 250000 250000 250000 5 1 250000 1 ...
result:
ok 500000 numbers
Test #5:
score: 0
Accepted
time: 1136ms
memory: 167340kb
input:
500000 500000 205699 141313 291987 999929528 111195 248994 999960789 391023 323134 92686 432395 316257 188889 219187 315056 39556 999959131 279778 30709 419259 242325 169515 137848 999905250 130641 245510 26 52987 999900052 144308 180276 162429 405263 130502 101937 108999 259339 137566 414011 304915...
output:
0 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 0 250000 3 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 0 250000 250000 250000 250000 250000 2 250...
result:
ok 500000 numbers
Test #6:
score: 0
Accepted
time: 1138ms
memory: 172468kb
input:
500000 500000 142817 198136 999910358 236637 238445 325614 22961 999909937 354352 999984540 189454 221148 208300 169118 999945163 256203 999945857 276295 175580 481676 114118 119423 999962365 999904418 250723 333971 311979 384475 386372 11544 999956892 999960490 999936512 292089 42395 5450 326202 26...
output:
0 250004 0 4 6 5 250004 6 250004 250004 0 0 250004 250004 250004 250004 0 0 250004 250004 250004 0 0 0 0 0 6 0 0 0 0 6 0 250004 4 250004 250004 250004 250004 250004 0 0 6 250004 6 250004 0 0 6 250004 4 250004 0 6 250004 250004 4 250004 0 6 0 250004 0 0 0 250004 4 0 0 6 0 0 0 6 0 250004 4 250004 5 25...
result:
ok 500000 numbers
Test #7:
score: 0
Accepted
time: 1180ms
memory: 166736kb
input:
500000 500000 273731 92547 391851 223257 245734 999907678 125748 999999710 260816 269057 173753 337309 208492 162862 160710 371998 296145 999901286 269727 36806 193730 999966618 219876 999919231 999950308 999989538 403483 27 199626 83765 58199 38349 999985326 362514 103279 96338 292486 353093 235704...
output:
0 250007 0 250007 250007 250007 250007 250007 250007 0 250007 0 250007 250007 250007 250007 250007 250007 250007 250007 250007 250007 250007 2 250007 250007 250007 250007 250007 250007 250007 250007 250007 250007 250007 250007 0 250007 250007 250007 250007 250007 250007 250007 250007 250007 250007 2...
result:
ok 500000 numbers
Test #8:
score: 0
Accepted
time: 1097ms
memory: 160928kb
input:
500000 500000 38066 263927 999904526 64975 999942253 139690 333059 341736 101159 145885 366360 999977224 58855 20369 491696 99014 999901769 497319 464130 118700 167144 197334 22373 266338 218334 344178 201845 470679 63936 29 473097 168465 91804 999907288 213685 441541 15210 999994423 241375 262928 1...
output:
0 249999 3 3 3 3 3 0 3 3 0 249999 3 249999 249999 249999 3 249999 249999 249999 3 249999 249999 3 249999 249999 249999 249999 249999 3 249999 249999 249999 3 249999 249999 249999 3 249999 3 249999 3 0 249999 3 249999 249999 249999 0 3 249999 249999 0 249999 249999 249999 249999 3 249999 0 0 0 3 3 3 ...
result:
ok 500000 numbers
Test #9:
score: 0
Accepted
time: 1113ms
memory: 166568kb
input:
500000 500000 359851 43247 193376 203439 213018 339470 255465 158106 353438 240598 296467 999940205 179011 999920003 999961598 416833 295334 64229 170166 444767 999928467 338236 9395 999990262 19653 322714 241284 499248 999981930 196853 232801 999979589 264041 137694 421299 35 156387 67567 38 221352...
output:
0 250001 250001 250001 13 250001 250001 250001 250001 250001 250001 250001 250001 250001 250001 250001 250001 250001 250001 250001 250001 0 250001 13 250001 250001 250001 250001 250001 250001 250001 250001 250001 0 250001 250001 250001 250001 250001 250001 250001 250001 250001 250001 250001 250001 2...
result:
ok 500000 numbers
Test #10:
score: 0
Accepted
time: 1088ms
memory: 165576kb
input:
500000 500000 62793 498516 201977 999910782 23738 94684 376404 165784 999984668 9 237448 417677 193394 999979378 207107 151870 11179 256917 96826 999936376 125873 70090 368693 23 80005 56086 38967 199021 222122 14684 84341 181399 999992500 417811 182996 231813 121859 226504 999926433 247806 128322 4...
output:
0 249999 0 0 249999 0 249999 249999 249999 0 249999 249999 249999 0 249999 249999 0 249999 249999 249999 249999 0 249999 249999 249999 249999 249999 249999 249999 249999 0 249999 0 249999 249999 249999 0 249999 249999 249999 249999 249999 2 0 249999 249999 249999 249999 0 249999 249999 249999 249999...
result:
ok 500000 numbers
Test #11:
score: 0
Accepted
time: 1159ms
memory: 163292kb
input:
500000 500000 372147 331053 216364 102319 487927 999930572 299860 157 213337 489912 248140 152140 267978 206747 14 132101 200350 194348 173014 485414 196543 3970 266852 157266 495915 333502 24668 96723 999915484 120906 268572 18354 180019 173961 169642 268928 364754 350491 264515 999926535 454505 11...
output:
0 250000 2 250000 1 250000 250000 250000 250000 1 0 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 0 250000 250000 250000 250000 250000 250000 0 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 2 250000 250000 250000 2500...
result:
ok 500000 numbers
Test #12:
score: 0
Accepted
time: 1204ms
memory: 163040kb
input:
500000 500000 10554 434273 130897 323091 259102 144593 2071 45944 411296 409399 149044 218944 287068 417164 999909168 471124 136115 180015 183512 999932545 221007 21 22 50559 379436 39555 304433 202728 344640 45046 165027 422037 168022 69739 34 194833 77845 164660 33088 109769 40 149910 236459 21921...
output:
0 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 2 249999 249999 2 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 2 249999 249999 249999 249999 24999...
result:
ok 500000 numbers
Test #13:
score: 0
Accepted
time: 1136ms
memory: 162996kb
input:
500000 500000 344899 5568 257238 360917 4 118728 110263 98091 365290 373265 230234 441644 83532 999911278 14 999955564 81214 17 206112 23116 443325 295321 17096 53413 226648 251673 66249 487707 258661 98934 999948086 43419 11185 999905728 999937426 445203 77498 207957 331814 300133 95465 51867 26432...
output:
0 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 250003 0 250003 250003 250003 250003 25...
result:
ok 500000 numbers
Test #14:
score: 0
Accepted
time: 1164ms
memory: 166696kb
input:
500000 500000 999957979 378969 37036 999976923 132503 126691 237168 248631 409168 999952617 226712 999971364 387270 360750 106052 999910264 1416 297566 336125 489882 78289 21 999973670 111583 188239 409935 429010 12181 999933993 89449 108495 15506 155044 153110 109451 497005 96792 9884 240956 999987...
output:
0 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 2 249999 249999 249999 249999 249999 249999 0 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 249999 0 249999 2 1 2...
result:
ok 500000 numbers
Test #15:
score: 0
Accepted
time: 1151ms
memory: 162212kb
input:
500000 500000 389972 445695 57960 999992103 181260 478090 442480 238400 92107 35808 496377 999970919 49853 95800 9724 15 999950506 427344 421081 999964891 231947 486953 75869 50981 166481 250659 327128 296434 40061 384891 95298 23035 999933227 115998 86190 14551 999914805 330917 99711 39811 98541 15...
output:
0 250000 250000 250000 250000 250000 250000 250000 0 250000 23 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 250000 8 250000 250000 250000 250000 250000 0 250000 25...
result:
ok 500000 numbers
Test #16:
score: 0
Accepted
time: 1089ms
memory: 153388kb
input:
500000 500000 160899 83708 999956721 116001 72511 207492 212355 65073 187736 9 337991 160783 220653 310467 18317 467640 999945604 222991 129636 286000 486761 42761 158760 497369 135755 102090 379616 999947096 999957305 313994 999908228 82387 89197 372359 244101 300795 150397 999982032 999955498 4878...
output:
0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 ...
result:
ok 500000 numbers
Test #17:
score: 0
Accepted
time: 1014ms
memory: 168948kb
input:
500000 500000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...
output:
0 250024 0 0 0 136214 0 0 250024 250024 250024 0 0 0 0 0 0 250024 250024 250024 0 0 250024 0 250024 250024 250024 0 0 250024 0 250024 250024 0 188431 250024 0 250024 0 235886 0 250024 250024 250024 0 250024 0 250024 150973 0 250024 250024 250024 0 0 0 0 0 250024 0 250024 250024 250024 0 250024 25002...
result:
ok 500000 numbers
Test #18:
score: 0
Accepted
time: 1104ms
memory: 178824kb
input:
500000 500000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...
output:
0 250242 250242 0 250242 0 250242 0 0 0 0 0 250242 250242 249765 0 0 0 0 250242 0 250242 0 250242 250242 0 250242 111162 68981 0 232259 250242 0 250242 0 188382 250242 0 249078 250242 0 0 0 0 0 0 250242 0 0 0 250242 0 250242 250242 0 0 250242 250242 250242 0 250242 250242 0 250242 250242 250242 0 25...
result:
ok 500000 numbers
Test #19:
score: 0
Accepted
time: 945ms
memory: 168816kb
input:
500000 500000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...
output:
0 250035 250035 250035 250035 250035 250035 250035 250035 250035 250035 0 250035 250035 0 0 250035 0 250035 250035 0 250035 70068 250035 250035 250035 250035 250035 250035 250035 250035 250035 250035 250035 250035 250035 250035 250035 250035 0 250035 250035 250035 250035 250035 250035 250035 250035 ...
result:
ok 500000 numbers
Test #20:
score: 0
Accepted
time: 913ms
memory: 166064kb
input:
500000 500000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...
output:
0 250233 250233 250233 250233 250233 250233 250233 250233 250233 250233 25654 0 250233 250233 250233 250233 250233 250233 250233 250233 250233 248693 250233 250233 250233 250233 250233 0 250233 250233 250233 250233 250233 250233 250233 250233 250233 250233 250233 250233 250233 250233 250233 250233 2...
result:
ok 500000 numbers
Test #21:
score: 0
Accepted
time: 1225ms
memory: 164744kb
input:
500000 500000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...
output:
0 250447 208490 208811 0 0 63548 0 250447 8882 21150 160870 133903 71184 194840 0 68425 30751 65729 219571 112843 0 250447 69834 191655 0 190132 0 179071 226688 0 0 0 183833 223897 250447 0 47193 92291 0 154652 0 250447 189392 250447 250447 247765 0 112408 59720 108124 100511 126898 198855 0 225181 ...
result:
ok 500000 numbers
Test #22:
score: 0
Accepted
time: 526ms
memory: 152976kb
input:
500000 1 159045 193900 999974833 3 999954042 999996219 425301 999999578 16228 61597 320935 134226 178894 71195 371140 347953 365582 163515 267457 132569 22439 227949 254340 455102 24 61800 74708 73738 302755 999969435 201404 360581 333960 43503 275248 35 127293 227282 111164 405480 251073 28467 3434...
output:
0
result:
ok 1 number(s): "0"
Test #23:
score: -100
Wrong Answer
time: 87ms
memory: 32600kb
input:
1 500000 0 1 0 1 3000000000 1 2004631033 1 715542462 1 1768462801 1 2989786132 1 2726091886 1 2259205577 1 362474676 1 1151951449 1 2117952161 1 2904847636 1 1556995443 1 2366732010 1 2372033576 1 288347569 1 776706498 1 2805710521 1 809149695 1 2456267663 1 780619499 1 1232031579 1 2587499917 1 213...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '1', found: '0'