QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#544436#6253. Appeal to the Audience CidoaiAC ✓17ms6296kbC++14577b2024-09-02 16:37:452024-09-02 16:37:45

Judging History

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

  • [2024-09-02 16:37:45]
  • 评测
  • 测评结果：AC
  • 用时：17ms
  • 内存：6296kb
查看
  • [2024-09-02 16:37:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+5;
int n,k,a[N],p[N];
int s[N],d[N],tp[N],x[N],tt;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<k;++i) scanf("%d",a+i);
	for(int i=1;i<n;++i) scanf("%d",p+i);
	for(int u=n-1,v;u;--u){v=p[u];d[u]=d[s[u]]+1;if(d[s[v]]<=d[u]) s[v]=u;}d[0]=d[s[0]]+1;
	for(int u=1,v;u<n;++u){v=p[u];if(s[v]==u) tp[u]=tp[v];else tp[u]=u;}
	for(int i=1;i<n;i++)if(tp[i]==i)x[tt++]=d[i];x[tt++]=d[0]-1;
	sort(a,a+k);sort(x,x+tt);
	ll ans=0;
	for(int i=0;i<k;++i) ans+=(ll)x[i]*a[i];
	printf("%lld",ans);
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3980kb

input:

5 3
5 4 3
0
0
1
1

output:

17

result:

ok single line: '17'

Test #2:

score: 0
Accepted
time: 0ms
memory: 5964kb

input:

11 7
30 5 15 1 3 100 50
0
0
1
0
2
5
2
5
5
1

output:

454

result:

ok single line: '454'

Test #3:

score: 0
Accepted
time: 13ms
memory: 5912kb

input:

99999 50000
776281622 281552176 560818893 743574034 28371581 29065388 861522831 399277410 127891403 337521653 333045937 201722127 532376484 866178821 488930207 533328467 280762095 777881963 698720876 926181033 678638871 483709812 805740065 609341704 534943664 598002301 497944186 842902577 127602924 ...

output:

74974456112141

result:

ok single line: '74974456112141'

Test #4:

score: 0
Accepted
time: 13ms
memory: 5456kb

input:

99999 50000
736607525 495413566 242981382 180522920 383406277 904059123 14931844 827592097 658904858 421611178 971164496 29212802 260869571 599952745 698370584 221201211 757581076 82619003 133169367 222890026 743399318 195978288 931589194 603744278 535433139 56057976 986499544 9144818 148181561 4159...

output:

66676571833058

result:

ok single line: '66676571833058'

Test #5:

score: 0
Accepted
time: 14ms
memory: 5728kb

input:

99999 50000
7889220 91966895 997494867 458839417 684433500 389172402 388831898 245383003 236972614 760799118 179373629 873232909 878046590 588830434 910521328 21768216 239703689 137113868 344804906 39866287 939755464 917587172 17113499 130080551 577455618 222721860 449364774 920498046 78566089 98504...

output:

66647877819405

result:

ok single line: '66647877819405'

Test #6:

score: 0
Accepted
time: 13ms
memory: 6296kb

input:

100000 99999
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1...

output:

99999000000000

result:

ok single line: '99999000000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

3 2
2 5
0
0

output:

7

result:

ok single line: '7'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

4 3
2 5 9
0
0
0

output:

16

result:

ok single line: '16'

Test #9:

score: 0
Accepted
time: 15ms
memory: 5840kb

input:

100000 58289
104308644 132511667 836253767 895735990 616652704 565820604 584206806 23079359 564999837 199862941 713790597 633357511 762731492 286619216 964365184 533588646 29439103 374560463 717534800 786774679 39306990 683139435 272435759 615991782 686244982 158502950 749458040 209082811 265999712 ...

output:

68265960527313

result:

ok single line: '68265960527313'

Test #10:

score: 0
Accepted
time: 15ms
memory: 5916kb

input:

100000 58158
109124680 221491555 354455225 738834575 380077866 331414382 614005110 341700295 45452532 775365165 860512321 830418242 344140238 566332016 716863935 739722298 412719063 504364008 130847792 726276755 6233145 24978091 329126653 551078659 910723586 327652006 296765944 244937138 490382135 8...

output:

68158471242483

result:

ok single line: '68158471242483'

Test #11:

score: 0
Accepted
time: 15ms
memory: 5940kb

input:

100000 58158
479046570 40139356 3564238 601477592 827199995 384720507 908627022 244871801 991378390 237555758 746327875 242884384 76488121 911341622 93283984 876143458 688787406 138309848 318693252 624861155 590897743 427702069 91610388 116221457 800147885 402178541 111240451 958150610 701269878 996...

output:

68347210005998

result:

ok single line: '68347210005998'

Test #12:

score: 0
Accepted
time: 14ms
memory: 5964kb

input:

100000 55572
707154754 226995160 580541354 454564666 483229606 795046720 293947340 583479271 926464249 331745005 237630393 830296444 40438244 447633583 922106430 211446839 49091676 750011488 347385487 653847418 86492208 777988241 316393106 242940972 490250163 570051947 166149357 392758545 881065040 ...

output:

70504679758794

result:

ok single line: '70504679758794'

Test #13:

score: 0
Accepted
time: 7ms
memory: 5952kb

input:

100000 55572
298257410 506613649 596699942 771410620 904340676 765079931 69526367 338010971 219781611 525903515 873047756 15340670 918991793 273185634 615298059 810534451 846018175 311192966 415334517 237110609 260191614 202578444 627204449 47185264 285602066 94030301 710813610 995250157 932964372 9...

output:

70673673886681

result:

ok single line: '70673673886681'

Test #14:

score: 0
Accepted
time: 15ms
memory: 5784kb

input:

100000 55568
753247759 860714500 376735682 744335121 398890520 896790946 553850384 381282960 760451289 307837004 212102954 946574503 663935362 251928255 577026459 502604071 30734288 979143816 644018877 955195511 584150293 857801585 477362419 168543465 372472477 678176494 93966679 295602579 249145462...

output:

70700737608669

result:

ok single line: '70700737608669'

Test #15:

score: 0
Accepted
time: 15ms
memory: 5920kb

input:

100000 56738
49052506 628406125 65777471 587572425 998164140 850396472 454444921 414442170 125774657 734908198 466622754 309319985 789523658 500257693 81091329 312882769 579199960 279966798 72062312 489646236 619749808 715267783 458279023 751299271 210611523 487783388 297817673 306427568 383928777 6...

output:

69617666068034

result:

ok single line: '69617666068034'

Test #16:

score: 0
Accepted
time: 15ms
memory: 6092kb

input:

100000 56738
480537709 963446902 420799990 151687861 651000347 867858737 26690315 421654396 452141810 998544923 18521768 640210570 314810221 369655731 675940136 318440243 137702158 427377343 644048795 135043191 744042090 78568808 354077497 530263380 829733239 846201414 947472259 731828058 707386742 ...

output:

69712225476259

result:

ok single line: '69712225476259'

Test #17:

score: 0
Accepted
time: 11ms
memory: 5864kb

input:

100000 56753
640410731 90780168 667804737 614827037 186813224 678218588 659011393 867279180 539575206 231238198 665064058 869561466 216933642 524329577 847288662 550472107 560658063 334282945 456727210 259706504 370482571 601591342 61417589 832954021 92591422 333687690 277610871 199193424 383540424 ...

output:

69595458340387

result:

ok single line: '69595458340387'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

10 8
161456015 309190776 89583694 694399129 319382447 289967878 405689762 732051672
0
0
0
0
0
0
3
3
0

output:

3733773045

result:

ok single line: '3733773045'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

12 7
784386116 119666423 710577708 476418261 503230656 101430310 687137240
0
0
1
1
4
4
2
2
0
5
5

output:

6446582770

result:

ok single line: '6446582770'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3980kb

input:

9 6
42590599 460350172 971872246 109680832 913204922 212720739
0
0
1
1
1
2
2
1

output:

4595496678

result:

ok single line: '4595496678'

Test #21:

score: 0
Accepted
time: 1ms
memory: 6004kb

input:

10 7
341636111 567178796 178940426 529953003 227158686 167060025 71002436
0
0
1
1
2
2
2
0
0

output:

3180061282

result:

ok single line: '3180061282'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

9 6
160880326 585089278 917866200 217948763 809332880 536594657
0
0
0
1
1
2
2
1

output:

4954911184

result:

ok single line: '4954911184'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3920kb

input:

8 5
15022585 913294575 61286752 228960544 581620606
0
0
1
1
2
2
0

output:

3295100243

result:

ok single line: '3295100243'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3924kb

input:

8 5
299069765 474526790 928456256 375990776 489161105
0
0
2
2
0
5
5

output:

3984822053

result:

ok single line: '3984822053'

Test #25:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

11 8
727152411 724695208 870169624 627219233 565615192 526271084 491060224 728690895
0
0
1
1
0
0
0
3
3
3

output:

7001213119

result:

ok single line: '7001213119'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

21 14
668659603 471478924 964893167 329292249 847905217 246684756 905490525 343179135 56292053 924573232 700863321 722953258 806897467 183337876
0
0
0
0
2
2
2
1
1
0
4
4
5
5
6
6
5
1
3
3

output:

13587153558

result:

ok single line: '13587153558'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

12 8
36251501 842170795 398655869 838234823 290940665 646871072 395635896 208221707
0
0
1
1
1
2
2
3
3
3
3

output:

6179558741

result:

ok single line: '6179558741'

Test #28:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

30 19
513652673 857847483 465396930 652869699 15472706 4387729 598310938 44713789 128499313 476207298 159461925 999289375 317644469 228959892 348908898 740781202 283817457 149309669 481960954
0
0
1
1
1
0
1
4
4
7
7
1
8
8
14
14
16
16
9
9
7
20
20
8
22
22
5
5
20

output:

16431132624

result:

ok single line: '16431132624'

Test #29:

score: 0
Accepted
time: 14ms
memory: 5876kb

input:

100000 99999
270290770 709171264 311532031 462470930 48294019 785442038 715645375 415113689 471394170 287096213 819337945 99743077 437539251 260054467 931625983 992878122 716959255 556524357 145076800 891284188 21746506 532868065 684420194 463589386 778007466 615241301 989372054 657113057 519819306 ...

output:

49919399235595

result:

ok single line: '49919399235595'

Test #30:

score: 0
Accepted
time: 15ms
memory: 5756kb

input:

99999 66666
689447014 601416478 504138566 407688083 361940258 870851014 32641297 913174894 551315171 516300437 163960851 224484817 190900946 237406155 894622553 673879696 323655456 895019283 635778445 608303524 572481770 54858181 567825398 816089611 289195081 145088028 893317662 478139602 69726358 6...

output:

62636549973892

result:

ok single line: '62636549973892'

Test #31:

score: 0
Accepted
time: 16ms
memory: 6008kb

input:

99999 66666
506523847 766652488 292805279 866649487 860568082 714234117 360536791 604477032 739482556 673032778 824274427 217938275 115654506 277340587 825294682 396305318 780402133 125355409 379461011 761847953 198150722 344556355 685077521 145248477 798963781 224079477 571647250 936716610 40918599...

output:

62661679031923

result:

ok single line: '62661679031923'

Test #32:

score: 0
Accepted
time: 17ms
memory: 5880kb

input:

100000 87500
159211229 761028175 223142762 973501905 757222993 201818040 849250334 298142011 239841055 923713537 597149690 473826510 151178229 968631474 163685119 759918401 289434322 50269979 464455564 373815753 689342508 784323071 508598526 356621965 403438936 761334510 887967259 951853530 87376230...

output:

55498268650333

result:

ok single line: '55498268650333'
English 繁體中文 简体中文

Server Time: 2024-12-02 16:57:30 | OpenSource Project