QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #825566 | #9905. 哈夫曼树 | guleng2007 | 30 | 57ms | 76716kb | C++20 | 2.7kb | 2024-12-21 20:24:21 | 2024-12-21 20:24:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int son[N*2][2], dist[N*2], fa[N*2], n;
long long a[N*2];
int lc[N*55], rc[N*55], cnt[N*55], root, indx;
long long fir[N*55], lst[N*55];
__int128 sum0[N*55], sum1[N*55], tot;
__int128 Hash(__int128 l,__int128 r)
{
return l*r;
}
void pushup(int& rt)
{
if(!lc[rt] && !rc[rt])
{
rt=0;
return;
}
if(!lc[rt])
{
fir[rt]=fir[rc[rt]], lst[rt]=lst[rc[rt]], sum0[rt]=sum0[rc[rt]], sum1[rt]=sum1[rc[rt]], cnt[rt]=cnt[rc[rt]];
return;
}
if(!rc[rt])
{
fir[rt]=fir[lc[rt]], lst[rt]=lst[lc[rt]], sum0[rt]=sum0[lc[rt]], sum1[rt]=sum1[lc[rt]], cnt[rt]=cnt[lc[rt]];
return;
}
fir[rt]=fir[lc[rt]], lst[rt]=lst[rc[rt]], cnt[rt]=cnt[lc[rt]]+cnt[rc[rt]];
sum0[rt]=sum0[lc[rt]]+(cnt[lc[rt]]%2==0?sum0[rc[rt]]:sum1[rc[rt]]+Hash(lst[lc[rt]],fir[rc[rt]]));
sum1[rt]=sum1[lc[rt]]+(cnt[lc[rt]]%2==1?sum0[rc[rt]]:sum1[rc[rt]]+Hash(lst[lc[rt]],fir[rc[rt]]));
}
void update(int& rt,long long l,long long r,long long pos,int val)
{
if(!rt)
rt=++indx;
if(l==r)
{
cnt[rt] += val;
if(cnt[rt]==0)
rt=0;
else
{
fir[rt]=lst[rt]=l;
sum0[rt]=cnt[rt]/2*(__int128)l*l;
sum1[rt]=(cnt[rt]-1)/2*(__int128)l*l;
}
return;
}
long long mid=(l+r)/2;
if(pos<=mid)
update(lc[rt],l,mid,pos,val);
else
update(rc[rt],mid+1,r,pos,val);
pushup(rt);
}
void query()
{
if(sum0[root]==tot)
printf("YES\n");
else
printf("NO\n");
}
void update(int x,long long y)
{
for(int i=fa[x];i;i=fa[i])
tot -= Hash(min(a[son[i][0]],a[son[i][1]]),max(a[son[i][0]],a[son[i][1]]));
if(fa[x])
update(root,1,1e15,a[x],-1);
a[x]=y;
if(fa[x])
update(root,1,1e15,y,1);
for(int i=fa[x];i;i=fa[i])
{
tot += Hash(min(a[son[i][0]],a[son[i][1]]),max(a[son[i][0]],a[son[i][1]]));
if(fa[i])
update(root,1,1e15,a[i],-1);
a[i]=a[son[i][0]]+a[son[i][1]];
if(fa[i])
update(root,1,1e15,a[i],1);
}
}
int main()
{
int q;
cin >> n >> q;
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(int i=n+1;i<=n*2-1;i++)
{
scanf("%d %d",&son[i][0],&son[i][1]);
fa[son[i][0]]=i, fa[son[i][1]]=i;
}
for(int i=n*2-1;i>=n+1;i--)
{
dist[son[i][0]]=dist[i]+1;
dist[son[i][1]]=dist[i]+1;
}
for(int i=1;i<=n;i++)
if(dist[i]>80)
{
for(int i=1;i<=q;i++)
printf("NO\n");
return 0;
}
for(int i=n+1;i<=n*2-1;i++)
{
a[i]=a[son[i][0]]+a[son[i][1]];
update(root,1,1e15,a[son[i][0]],1);
update(root,1,1e15,a[son[i][1]],1);
tot += Hash(min(a[son[i][0]],a[son[i][1]]),max(a[son[i][0]],a[son[i][1]]));
}
query();
for(int i=1;i<=q-1;i++)
{
int x;
long long y;
scanf("%d %lld",&x,&y);
update(x,y);
query();
}
return 0;
}
詳細信息
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 0ms
memory: 14000kb
input:
3 4 1 1 1 2 3 1 4 2 2 1 2 3 3
output:
YES NO YES NO
result:
ok 4 token(s): yes count is 2, no count is 2
Test #2:
score: 30
Accepted
time: 0ms
memory: 14040kb
input:
8 5 5 3 4 2 2 6 5 5 1 8 4 5 10 3 11 9 7 2 6 13 14 12 7 3 6 8 4 2 2 5
output:
NO YES YES YES NO
result:
ok 5 token(s): yes count is 3, no count is 2
Test #3:
score: 30
Accepted
time: 4ms
memory: 22100kb
input:
5 1000 193989534544158 57483670601746 183281373434588 92196008024549 197513473286508 1 5 4 2 7 3 8 6 2 65545142774024 4 67957472319495 5 131478473459166 2 102185858570152 3 191441353035940 5 186000528093501 2 63201184033501 2 77481806092413 3 159789430863849 4 92773786021894 1 194598667478593 3 1458...
output:
YES YES YES NO NO NO NO NO NO YES YES YES YES YES YES YES YES NO NO YES YES YES YES YES YES NO NO NO NO YES NO YES YES YES YES YES YES NO NO NO NO YES YES YES NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES YES YES YES NO NO NO NO NO YES NO NO NO NO NO NO YES ...
result:
ok 1000 token(s): yes count is 375, no count is 625
Test #4:
score: 30
Accepted
time: 3ms
memory: 21352kb
input:
7 1000 88159166205053 95998544558881 48231159865354 231786835189365 84291070100955 225941839972605 33315221625793 2 5 6 4 7 3 1 10 8 11 9 12 6 150843468162951 2 75759088055460 1 86133344610051 4 140694127444493 1 63070113756930 1 90150689680608 6 147790469610032 7 46561924657801 2 103953340734616 6 ...
output:
NO NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 1000 token(s): yes count is 86, no count is 914
Test #5:
score: 30
Accepted
time: 3ms
memory: 14116kb
input:
7 1000 5 6 7 3 2 5 5 4 7 3 5 1 2 10 6 8 9 12 11 5 2 5 1 5 1 1 2 3 2 5 1 5 2 6 3 4 2 4 1 2 1 5 1 5 1 5 1 7 1 1 2 5 1 5 1 6 3 6 3 5 1 2 2 7 2 7 1 7 1 2 2 1 2 4 2 4 1 1 1 3 1 5 1 2 2 2 2 4 1 2 1 7 2 6 1 2 1 6 2 5 2 1 1 1 1 6 3 7 2 6 3 4 1 1 1 5 1 2 2 7 2 5 1 4 2 5 2 7 2 7 1 4 1 3 2 3 2 1 1 7 2 5 2 1 1 ...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO YES YES YES YES NO YES NO YES YES YES YES YES YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO YES NO NO NO NO NO NO NO YES YES YES YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 1000 token(s): yes count is 199, no count is 801
Test #6:
score: 30
Accepted
time: 8ms
memory: 26976kb
input:
8 1000 172480280419267 212072146993988 23147786306112 161006134777989 37963466387491 50018942108886 18649770050090 50499101532214 7 3 2 1 5 8 9 6 12 11 4 13 10 14 5 57899673021751 7 22087918088240 1 236990257757485 3 21994370580136 7 26427284121647 8 54391900162086 7 27709763713585 6 59631479929866 ...
output:
NO NO NO YES YES YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO YES NO YES NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES...
result:
ok 1000 token(s): yes count is 119, no count is 881
Test #7:
score: 30
Accepted
time: 3ms
memory: 23052kb
input:
6 1000 20326746134626 98517002313418 165556087937310 116347939244398 130872245741329 136674587230071 2 3 6 7 8 1 9 5 10 4 4 31902652070998 2 20697837065544 3 14389422108471 5 45879772826060 2 23505088168423 6 7588643182717 2 13873224035289 4 3462171437780 6 12963735380517 6 3348685354818 3 141429739...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO...
result:
ok 1000 token(s): yes count is 12, no count is 988
Test #8:
score: 30
Accepted
time: 40ms
memory: 23584kb
input:
72 1000 2 10946 610 987 139583862445 20365011074 5 1597 196418 377 267914296 44945570212853 956722026041 5702887 39088169 75025 27777890035288 12586269025 4181 1 53316291173 144 1548008755920 63245986 1 225851433717 6557470319842 832040 2504730781961 102334155 55 3 46368 7778742049 6765 165580141 72...
output:
YES NO YES NO YES NO YES NO YES YES YES NO YES NO YES NO YES YES YES NO YES NO YES NO YES NO YES NO YES NO YES YES YES NO YES NO YES NO YES YES YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES YES YES NO YES NO YES NO YES NO YES NO YES NO YES YES YES NO YES NO YES YES YES YES YES N...
result:
ok 1000 token(s): yes count is 598, no count is 402
Test #9:
score: 30
Accepted
time: 42ms
memory: 33328kb
input:
70 1000 31322671994689 1078810887856 579849 254672704401 136883 4713 4569916255830 11964196083506 19970 22963823428 157396387326 488813369 12341 1 61 1799 162 82003819900560 221480 5421023350 44076273 37 261 347373755513422 6430641 938216 71316908 687 7394279827673 302103276 2456284 32311 1745552683...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...
result:
ok 1000 token(s): yes count is 986, no count is 14
Test #10:
score: 30
Accepted
time: 38ms
memory: 71340kb
input:
1000 1000 696394773309 108383178182 819893348793 723784375461 931503257800 952660789032 100236017416 539829053718 209653090976 981815062655 964960614840 961643834067 369486282052 800646303984 387416608811 261777906950 172691588923 485971148690 453102872226 770561490733 375803723200 861225005889 1185...
output:
YES NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO YES NO NO YES YES YES YES YES YES YES NO NO NO NO NO NO YES YES YES YES NO NO YES YES NO YES YES NO NO NO NO NO NO NO YES YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO ...
result:
ok 1000 token(s): yes count is 290, no count is 710
Test #11:
score: 30
Accepted
time: 57ms
memory: 76716kb
input:
1000 1000 328753409716 63174357177 116706499724 751756098545 913879475315 309225707947 610363994448 928602608183 298378305770 255654307269 444288397875 332511908079 297834684008 532592347055 268793918986 782156365515 316531786356 584037378094 809660826672 456709928147 277332 603219716866 60062165567...
output:
YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO YES NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO ...
result:
ok 1000 token(s): yes count is 124, no count is 876
Test #12:
score: 30
Accepted
time: 18ms
memory: 37120kb
input:
1000 1000 596779917266 859728384612 790999537569 946122172426 539615683280 616114813176 675147442971 523252967306 989540738771 880850130723 850501333358 858531013132 700803829612 642617589194 814265292894 799430766156 589454900606 735369030885 797404510621 602718454036 883696282103 974675349909 7793...
output:
YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 1000 token(s): yes count is 3, no count is 997
Test #13:
score: 30
Accepted
time: 30ms
memory: 56092kb
input:
1000 1000 12340874 29443 42 12492 139286 153819 53474891 4999 5513602 15 15542744701 367380 19381 1390668 27542397298 328751473 10398280 3528202605 126026926 21552 4031001 14293341319 140519268911 360904 1422 28 13089 32427234919 457240409937 17711545787 39539446 51 355784231 810175146335 916553144 ...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES YES YES YES NO NO YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO NO YES YES YES YES YES YES YES Y...
result:
ok 1000 token(s): yes count is 749, no count is 251
Test #14:
score: 30
Accepted
time: 12ms
memory: 21008kb
input:
1000 1000 19 27 18 26 41 49 29 27 46 24 43 25 50 4 17 25 15 15 4 33 24 35 10 7 27 3 39 43 36 28 29 5 20 5 42 43 33 17 11 26 43 21 38 31 12 33 48 33 14 29 48 49 15 37 16 4 16 44 25 45 41 17 37 49 32 40 9 12 8 22 2 24 9 21 14 16 34 45 47 25 28 16 26 7 11 42 26 29 35 32 34 44 11 30 20 47 13 6 41 19 37 ...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 1000 token(s): yes count is 468, no count is 532
Test #15:
score: 30
Accepted
time: 0ms
memory: 7908kb
input:
1000 1000 996069901379 940888328260 925342655682 923520191546 877076702411 855421610507 842224729549 837033687452 810175146335 792646717951 752993949814 717579080665 711089804069 708221643771 699280599587 697696794210 670880120082 641841749136 631447339331 619769332589 617930141820 586690159836 5636...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 1000 token(s): yes count is 0, no count is 1000
Subtask #2:
score: 0
Runtime Error
Test #16:
score: 0
Runtime Error
input:
10000 10000 85117964119 41472951000 61693640396 66409648221 91978532661 62922448518 92497200794 43837348258 45577855926 38256001396 79446271832 95289903258 62510175551 97599809584 56162244722 87617641117 64010325734 56604859803 58544571483 40687963085 38627694508 64665875035 62273927372 73014847094 ...
output:
YES YES YES YES NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
Subtask #3:
score: 0
Runtime Error
Test #20:
score: 0
Runtime Error
input:
50000 50000 16394396247 17456058492 11358090355 13208121167 8612535629 2853817504 18100755237 18603321637 1618810635 7615832530 13631222424 7817630977 10963098997 19654927084 645638016 9352759139 17939720223 15106346489 14475376391 2122412099 15482023637 11224675857 15931143509 4240408932 1270948838...
output:
YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO...
result:
Subtask #4:
score: 0
Runtime Error
Test #24:
score: 0
Runtime Error
input:
70 100000 66748 126 1 91045172 3605661959574 274077743637349 147314183 8209537 740253 6920630855 25494 1377240316614 15756 6 108000 18118446805 169389361127761 29316262755 48 2643445763 5834083602536 3 9439745562111 29 3719 10 47434709561 11197815949 6018 325122336074 851181326345 1633739329 1527382...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...