QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#619368#2999. 春节十二响McIron233100 ✓134ms128896kbC++14733b2024-10-07 14:00:192024-10-07 14:00:20

Judging History

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

  • [2024-10-07 14:00:20]
  • 评测
  • 测评结果:100
  • 用时:134ms
  • 内存:128896kb
  • [2024-10-07 14:00:19]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define N 2000005
using namespace std;
int n,ans,a[N],maxx[N];
vector<int>e[N],o;
priority_queue<int>q[N];
void merge(int x,int y) {
	if(q[x].size()<q[y].size())swap(q[x],q[y]);
	while(q[y].size()){
		o.push_back(max(q[x].top(),q[y].top()));
		q[x].pop(),q[y].pop();
	}
	while(o.size())q[x].push(o.back()),o.pop_back();
}
void dfs(int x){
	for(unsigned int i=0;i<e[x].size();i++){
		dfs(e[x][i]);
		merge(x,e[x][i]);
	}
	q[x].push(a[x]);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=2;i<=n;i++){
		int x;cin>>x;
		e[x].push_back(i);
	}
	dfs(1);
	while(q[1].size()){
		ans+=q[1].top();
		q[1].pop();
	}
	cout<<ans;
	return 0;
}

详细


Pretests


Final Tests

Test #1:

score: 5
Accepted
time: 15ms
memory: 115236kb

input:

3
4 10 5
1 2

output:

19

result:

ok single line: '19'

Test #2:

score: 5
Accepted
time: 11ms
memory: 115108kb

input:

5
10 8 1 1 7
1 1 2 2

output:

25

result:

ok single line: '25'

Test #3:

score: 5
Accepted
time: 17ms
memory: 115416kb

input:

10
1 2 2 1 1 2 1 1 1 2
1 1 1 2 5 5 5 8 1

output:

7

result:

ok single line: '7'

Test #4:

score: 5
Accepted
time: 15ms
memory: 115280kb

input:

10
1 1 2 1 2 2 1 2 1 1
1 2 3 4 3 6 2 1 6

output:

7

result:

ok single line: '7'

Test #5:

score: 5
Accepted
time: 8ms
memory: 115620kb

input:

15
5 9 5 1 7 3 8 3 1 7 3 1 1 5 8
1 2 2 2 4 1 5 1 2 9 7 12 1 12

output:

25

result:

ok single line: '25'

Test #6:

score: 5
Accepted
time: 7ms
memory: 116824kb

input:

16
8 9 19 9 13 9 17 8 9 20 20 7 2 12 19 6
1 2 1 4 3 5 5 8 6 10 3 8 7 4 3

output:

85

result:

ok single line: '85'

Test #7:

score: 5
Accepted
time: 11ms
memory: 116280kb

input:

16
177269241 136479857 518040716 590690929 837228149 71462256 887232525 317436776 138552464 727415824 697621256 859965262 588521417 821100487 594324041 92665222
1 2 1 1 2 2 3 3 5 8 3 8 5 3 5

output:

2339518886

result:

ok single line: '2339518886'

Test #8:

score: 5
Accepted
time: 16ms
memory: 116348kb

input:

16
439163150 802894105 828281100 29854078 492638605 752259707 917086603 810075381 743328523 497018778 360212988 603293784 85540195 33829826 50134176 30721768
1 1 2 3 1 3 7 1 3 4 10 2 9 3 3

output:

2994606234

result:

ok single line: '2994606234'

Test #9:

score: 5
Accepted
time: 13ms
memory: 115800kb

input:

16
95 84 71 72 11 77 100 97 72 93 90 77 1000 33 19 31
1 1 3 3 1 2 5 2 3 8 9 12 5 7 3

output:

1334

result:

ok single line: '1334'

Test #10:

score: 5
Accepted
time: 62ms
memory: 122676kb

input:

100000
51 23 6 31 25 88 47 2 84 90 10 56 97 84 51 74 85 64 21 29 20 21 62 62 36 30 81 82 91 62 53 94 36 10 76 60 49 22 14 32 64 23 39 60 58 90 34 43 53 6 71 24 78 84 86 13 65 18 46 56 79 50 1 66 59 76 26 60 49 91 91 12 13 30 72 70 71 5 64 75 62 86 98 39 69 35 3 34 53 48 41 31 49 93 49 7 20 26 66 68 ...

output:

2529557

result:

ok single line: '2529557'

Test #11:

score: 5
Accepted
time: 93ms
memory: 128896kb

input:

150000
1780 14021 14043 16222 20687 24893 42032 47007 49300 52496 55196 60042 61228 69764 76485 77097 79859 80602 89003 92297 99254 101745 110985 117001 123788 128038 128171 136063 138089 141214 144843 157181 163051 165982 169166 170552 175768 180315 184163 188339 190724 191813 192841 199155 204364 ...

output:

35463479060852

result:

ok single line: '35463479060852'

Test #12:

score: 5
Accepted
time: 92ms
memory: 127616kb

input:

150000
797908089 784987073 46944837 930191726 921098399 310954288 142542503 183158851 498350060 133840827 989090507 980304605 709717903 683657094 583791273 318822313 942189883 219717636 361991649 141603401 9012971 822131679 188198712 434976006 71544379 947141339 106477492 141627901 988298100 4059125...

output:

35453836287189

result:

ok single line: '35453836287189'

Test #13:

score: 5
Accepted
time: 15ms
memory: 116952kb

input:

2000
100 71 65 47 56 12 42 30 54 22 36 97 92 38 84 99 64 57 85 98 39 25 11 17 20 26 66 81 92 64 37 43 35 1 41 42 65 35 71 18 56 6 14 47 95 49 97 10 57 81 59 47 5 69 63 77 95 29 57 38 44 46 81 30 98 21 71 62 55 93 31 10 50 44 8 45 44 57 54 100 37 13 47 94 33 61 70 27 89 78 17 85 23 97 14 21 17 37 82 ...

output:

19842

result:

ok single line: '19842'

Test #14:

score: 5
Accepted
time: 15ms
memory: 116840kb

input:

2000
1 3 5 5 7 8 9 10 11 11 12 12 12 12 12 13 13 13 14 14 15 16 16 16 17 17 18 21 22 22 23 23 23 25 25 25 26 26 27 28 28 28 28 28 28 29 29 29 30 31 31 32 32 33 33 35 36 36 37 37 37 38 39 39 39 40 41 41 41 41 42 42 42 42 43 43 44 45 45 46 46 47 48 48 49 49 50 50 51 51 52 52 52 52 53 53 53 53 54 54 55...

output:

198663

result:

ok single line: '198663'

Test #15:

score: 5
Accepted
time: 24ms
memory: 117148kb

input:

2000
1 1 3 3 4 4 4 5 5 7 7 7 7 7 8 8 9 9 9 10 10 11 11 12 12 12 13 13 14 14 14 14 14 15 15 16 16 16 17 17 17 17 18 18 19 19 19 20 20 21 21 23 24 24 25 25 27 27 27 27 28 28 29 29 29 30 30 31 31 32 32 32 32 33 34 34 34 34 35 35 35 37 38 39 39 40 40 41 42 42 44 44 45 46 46 46 46 48 49 50 51 51 51 51 52...

output:

175767

result:

ok single line: '175767'

Test #16:

score: 5
Accepted
time: 95ms
memory: 125176kb

input:

200000
753 856 722 833 51 114 999 177 365 374 755 761 420 327 354 357 834 691 665 533 926 768 823 753 332 726 832 11 103 774 30 855 982 751 39 32 216 389 561 580 114 315 693 533 993 46 242 178 88 906 710 13 673 884 118 357 610 949 367 712 723 397 918 704 499 308 87 715 696 647 294 161 313 338 693 30...

output:

18276228

result:

ok single line: '18276228'

Test #17:

score: 5
Accepted
time: 92ms
memory: 124992kb

input:

200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

18171535

result:

ok single line: '18171535'

Test #18:

score: 5
Accepted
time: 128ms
memory: 127416kb

input:

199999
823285901 477166963 348450438 320236141 201658155 230106556 298811949 201089971 578905148 921146489 55355606 661735064 864805465 934691341 805255537 654582721 368495076 22691277 28126605 645131210 633602063 438131799 214756248 647514920 480491658 906960147 142206414 397775189 633189604 618961...

output:

17018327325681

result:

ok single line: '17018327325681'

Test #19:

score: 5
Accepted
time: 134ms
memory: 125068kb

input:

199998
787276771 914335740 739025048 444916565 545108873 429907832 521181033 625114241 123679075 635504340 432788154 751979906 270531673 870643710 528513199 630155900 983812400 610529578 918361469 61376025 915950583 491917202 6303438 639611089 695103305 30836351 854978506 863964151 713886031 6278892...

output:

17174054861956

result:

ok single line: '17174054861956'

Test #20:

score: 5
Accepted
time: 112ms
memory: 125140kb

input:

199997
541412948 31954496 577614307 653157996 354253149 377225109 594337307 128057389 106954411 85250057 953326084 107845778 518626668 969193653 882540733 305581838 730205341 84480784 267127777 383392198 8062772 547669300 824385066 911658679 550924598 468293145 447934189 599967513 103929466 18513528...

output:

17135092871559

result:

ok single line: '17135092871559'

Extra Test:

score: 0
Extra Test Passed