QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#431333 | #5830. 树 | Doqe | 10 | 3962ms | 204304kb | C++17 | 2.0kb | 2024-06-05 12:47:48 | 2024-06-05 12:47:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,B=20;
int n,I,U;
struct node
{
long long vl[N],u1[N],u2[N],tmp[N];
int Z;
pair<long long,long long>ask(int d,int k)
{
long long ans=0;
long long v1=vl[d ]-vl[d+U/2 ],
v2=vl[d+U/2 ]-vl[d+U ];
int r =(k&U-1),z=k-r;
if(r<U/2)
{
v1-=vl[d+U+z]-vl[d+k+1+U];
v1-=vl[d+k+1]-vl[d+U/2+z];
v2-=vl[d+U/2+z]-vl[d+U+z];
}
else
{
v1-=vl[d+z+U]-vl[d+z+U/2+U];
v2-=vl[d+z+U/2+U]-vl[d+k+1+U];
v2-=vl[d+k+1]-vl[d+U+z];
}
return make_pair(v1,v2);
}
void shrink(int W)
{
while(Z>W)
{
if(Z>U)u2[Z-U]+=u2[Z];
u1[Z]+=u2[Z];u1[Z-1]+=u1[Z];
vl[Z]+=u1[Z];u1[Z]=u2[Z]=0;--Z;
}
}
void ins(int d,int v){Z=max(Z,d),u2[d]+=v,tmp[d]+=v;}
}V,C;
int tmp[N];
vector<pair<int,int>>Q[N];
vector<int>to[N];
int v[N];
long long ans[N];
void ins(int d,int v){V.ins(d,v>>I&1),C.ins(d,1);}
void shrink(int W){V.shrink(W),C.shrink(W);}
long long ask(int d,int k)
{
auto k1=V.ask(d,k),k2=C.ask(d,k);
return (0ll+k1.first+k2.second-k1.second)<<I;
}
void dfs(int u,int f,int D)
{
// cerr<<"DFS: "<<u<<" "<<f<<" "<<D<<" "<<v[u]<<endl;
// shrink(0);
// for(int j=1;j<=n;++j)
// cerr<<C.tmp[j]<<",";
// cerr<<" \n";
// for(int j=1;j<=n;++j)
// cerr<<C.vl[j]<<",";
// cerr<<" \n";
for(int j=1;j<=n;++j)
{
auto x=C.ask(j,2);
// cerr<<x.first<<" "<<x.second<<endl;
}
for(auto k:Q[u])ans[k.second]-=ask(D,min(k.first,n-D));
// assert(V.Z==C.Z&&V.Z==D-1);
ins(D,v[u]);
for(int v:to[u])dfs(v,u,D+1);
shrink(D-1);
for(auto k:Q[u])ans[k.second]+=ask(D,min(k.first,n-D));
}
int main()
{
cin>>n;for(int i=1;i<=n;++i)cin>>v[i];
for(int i=2,u;i<=n;++i)cin>>u,to[u].push_back(i);
int q;cin>>q;for(int i=1,x,k;i<=q;++i)cin>>x>>k,Q[x].emplace_back(k,i);
for(int i=0;i<B;++i)
{
#define mem(z) memset(V.z,0,sizeof V.z);memset(C.z,0,sizeof C.z)
mem(tmp);mem(vl);mem(u1);mem(u2);V.Z=C.Z=0;
I=i,U=(1<<I+1);dfs(1,0,1);//for(int i=1;i<=q;++i)cerr<<ans[i]<<",";cerr<<endl;
}
for(int i=1;i<=q;++i)cout<<ans[i]<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 79ms
memory: 118548kb
input:
2000 946347867 341162491 202762650 295215762 254064439 66267204 693162580 357612557 492940637 939526638 59775103 374919339 144042807 861369313 651043728 999024805 439554916 167782038 597475252 56704409 69846137 22185655 79439847 769194737 145071391 226046618 915359433 392527325 84982946 54584098 827...
output:
37932691 905377 818187 947775646 95835818 91750 1196813 406650 8529810 56023191 952346 1383109 68400197 1985223 126774585 97356808 437880913 1590093 149493994 974590 185637 25041923 319721 119584744 504577 555834 869981 528001 51244174 647662 3161756 365090 1438245 3285067 231136 162680380 28654882 ...
result:
wrong answer 1st numbers differ - expected: '31727996563', found: '37932691'
Test #2:
score: 0
Wrong Answer
time: 326ms
memory: 127908kb
input:
99999 792064428 473106195 799314986 65440734 948726345 442414256 280245405 873012700 466192412 899092866 283555341 657824017 963883713 793944180 767444438 105576842 542107696 580140098 65321660 381184238 584604194 397414881 861590124 309323011 217641157 120832524 303744205 961590116 110259426 380351...
output:
2625803 107169001 1466128 647187 1445647 2768682770 5629373870 517597 4490383745 932285 188444 3209058 824954 2640784 3677283243 34176692147 834665 425551 2895214718 17022891662 797022 1707885 1662879321 4666 2427613895 2090583 1471578 347199 682143 991482 254675723 436243 765392 8855457701 68532027...
result:
wrong answer 1st numbers differ - expected: '2509771019', found: '2625803'
Test #3:
score: 0
Time Limit Exceeded
input:
1000000 947727010 179844140 923847675 171881267 5552129 974443359 989307850 869400987 126992154 527448411 141137718 136124474 917813105 392020809 79012342 473860575 969007624 833563354 90169336 878445705 84352622 403307122 733751738 670851448 942399068 731541999 101293644 545785337 964751520 9168003...
output:
result:
Test #4:
score: 0
Time Limit Exceeded
input:
1000000 264862971 751386013 921867736 711577153 262726588 565608444 975324815 440219681 107888226 928241413 729126923 283912914 86248857 896446999 12839598 651796991 139813366 105131395 341646170 839485925 939265720 844548518 102280410 457829889 8602879 737140565 17206920 974175632 535833885 8373832...
output:
result:
Test #5:
score: 0
Wrong Answer
time: 3714ms
memory: 193676kb
input:
1000000 978606419 773027389 111265179 979476504 280718851 476857501 751854950 579263969 848569548 781051974 31782627 533831186 812822170 111553645 297770650 331144396 676977983 2236128 258203325 75591120 676466973 60056446 494411414 286185093 92474576 173276071 535648669 87210101 355790411 880267291...
output:
2291109 311102 1768259 23407466 15080873 2613813 15615600 3591038 1474265 740607 402151 2588658 19276905 428254 958561 45544 3225432 4938254 2185253 25957264 4694262 7988311 685428 17060163 306679 507627 5526787 567735 2370719 10496720 709692 21854104 430631 887697 489340 15042189 1688463 148768 231...
result:
wrong answer 1st numbers differ - expected: '2258826661', found: '2291109'
Test #6:
score: 0
Wrong Answer
time: 3953ms
memory: 196500kb
input:
1000000 952470566 585754087 120174600 401525004 458588768 5487567 31210348 446333263 231409083 521960132 457721893 866842852 925207283 16805978 4706826 99640835 619272676 136536623 459247161 308807462 633687300 717271369 23906473 865522890 173799280 424309108 719410673 118906385 110627845 730629403 ...
output:
1166 184930 1594315 4516519572 39318584227 1076268 603138 768964 440211 1856000 73782578565 20741 893711 116819831244 15399178684 570331 1660567 1006940 915441 109596298287 187777 543671 881369 25572542342 108539791753 296867 1445416 865429 83716675507 1340077 6749004 1437999 1345333 1186415 1990786...
result:
wrong answer 1st numbers differ - expected: '994051214', found: '1166'
Test #7:
score: 0
Wrong Answer
time: 3962ms
memory: 204304kb
input:
1000000 732367509 105027907 958920212 886798715 102486738 813075884 301085392 242303497 979657287 944859684 307768 438158233 561755409 740706505 791145209 283862713 828081846 771569552 59044985 600549571 191330226 438693570 36976319 810654215 220068818 771875421 740642902 839964155 206129566 2065543...
output:
1664401 165871 230254397138 216630424166 63561960373 120137391493 1666851 112387194009 3937460 5259799 694503 1429904 17284 10479218165 82744070780 482008 64871766428 1515482 57780188521 465137365083 110374036813 880740 3804013 41577324296 32934266753 112310815598 352902 235209342829 27816014631 194...
result:
wrong answer 1st numbers differ - expected: '999908753', found: '1664401'
Test #8:
score: 10
Accepted
time: 3879ms
memory: 201464kb
input:
1000000 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 ...
output:
3826404725 4857376598 25168931 28 7223089410 64321117 0 334067473 60992 1 3 1 1 1 1 0 672988753 1 0 3075365115 8 0 0 3 0 320487913 1 0 0 0 0 423617904 687492110 0 301348 220115086 10 35419106 37297971 1 1 28561996 517977935 3 2643348428 0 1132906086 2 1 4 20029285275 6 6191566989 0 20341562923 93968...
result:
ok 1000000 numbers
Test #9:
score: 0
Time Limit Exceeded
input:
1000000 465660691 982007525 816592310 377030959 572981469 679249520 86377999 709561525 940473306 35102782 886143915 792819787 903287397 264564177 857982095 91486434 217197704 123118964 383387342 820268798 497623987 255010796 607884194 848568529 38169627 197987657 421323589 664004905 485409127 696844...
output:
104323247 9143173467 92488791967 38000673535 673742 2211486 753432 13157855320 11304718932 291497234 17432417928 965125 1299937 493680 14519532879 406365 31708653759 422572 687047 54105771685 90429845361 908073 19696551641 1038145 2582323435 31312439713 991868 386489833 341221 14499108707 3920577747...
result:
Test #10:
score: 0
Time Limit Exceeded
input:
1000000 665830082 788228483 245541444 289601309 641764988 150723484 925214020 557415731 310210969 379707835 517820381 883917428 134445288 775557009 444476671 89856268 655841087 888410254 37788122 694551869 563331754 488108584 839551943 415095075 445425438 35452604 562044723 640544531 146258096 66852...
output:
891307 279920 86379675063 7808882573 70374751786 15356527124 749156 5579855565 636472 1013495 2988546921 28578008118 1114823 634153 84034026260 694576 35139896344 2025620 5594490638 307067 20767736460 1247924 9993914777 6373182291 192959 2518973 541401 29399513782 774509 1429983 197992400847 883992 ...