QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#431333#5830. 树Doqe10 3962ms204304kbC++172.0kb2024-06-05 12:47:482024-06-05 12:47:49

Judging History

你现在查看的是最新测评结果

  • [2024-06-05 12:47:49]
  • 评测
  • 测评结果:10
  • 用时:3962ms
  • 内存:204304kb
  • [2024-06-05 12:47:48]
  • 提交

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
...

result: