QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#182819#4406. 独立集问题Fy5Fengye6 105ms65624kbC++1.1kb2023-09-18 16:18:062023-09-18 16:18:06

Judging History

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

  • [2023-09-18 16:18:06]
  • 评测
  • 测评结果:6
  • 用时:105ms
  • 内存:65624kb
  • [2023-09-18 16:18:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define F(i,j,k) f[i][j][k]
const ll INF=1e18,N=400005;
ll a[N],f[N][3][2];
vector<int>go[N];
ll mx(ll f[2]) {return max(f[0],f[1]);}
inline void dfs(int u)
{
    F(u,0,0)=a[u],F(u,0,1)=-a[u];
    F(u,1,0)=F(u,1,1)=-INF;
    F(u,2,0)=F(u,2,1)=0;
    for(int v:go[u])
    {
        dfs(v);
        for(int i:{0,1})
        {
            F(u,0,i)+=max(mx(f[v][1]),mx(f[v][2])+a[v]*(i?1:-1));
            F(u,1,i)=max(F(u,1,i)+max(max(mx(f[v][0]),mx(f[v][1])),mx(f[v][2])+a[v]*(i?1:-1)),F(u,2,i)+max(max(F(v,0,0),F(v,1,0))-a[u],max(F(v,0,1),F(v,1,1))+a[u]));
            F(u,2,i)+=max(max(mx(f[v][0]),mx(f[v][1])),mx(f[v][2])+a[v]*(i?1:-1));
        }
    }
}
inline int read()
{
    int ret=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) ret=ret*10+ch-'0',ch=getchar();
    return ret;
}
int main()
{
    int n; n=read(); for(int i=1;i<=n;++i) a[i]=read();
    for(int i=2;i<=n;++i) go[read()].push_back(i); dfs(1);
    cout<<max(mx(f[1][0]),mx(f[1][1]))<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 41ms
memory: 65624kb

input:

351493
-641495974 -401868912 -864400429 35718599 -579296290 767835327 149511992 -246228754 649472235 893048442 -292675192 -788090312 -578172296 -62289673 196890164 -120059197 -452848333 -216788131 -604555771 -240241020 376984486 -407661514 -107574590 -461679558 -470560314 -583391402 -991686079 76956...

output:

175477002771369

result:

wrong answer 1st numbers differ - expected: '175477002777567', found: '175477002771369'

Subtask #2:

score: 6
Accepted

Test #21:

score: 6
Accepted
time: 42ms
memory: 42220kb

input:

351493
915594742 688454502 456077914 208864399 625937959 102483811 538999077 529481828 400375958 387560315 83710527 83424975 330114353 684812426 68052931 28849220 295907801 535129167 967891325 124069427 644256858 757666812 558755455 178666038 177054898 795236216 848264282 669310447 328353372 3681163...

output:

175766699890054

result:

ok 1 number(s): "175766699890054"

Test #22:

score: 0
Accepted
time: 77ms
memory: 41524kb

input:

351493
558106095 906433626 370590649 172443229 359294152 56072006 85811676 997806511 819710547 234550001 616962251 426062666 836364151 264171065 793148682 129635867 178265836 843676703 590478956 841451015 534070481 684617914 671870778 955426286 402736154 219850741 31973708 468849347 318576756 566186...

output:

175789713405292

result:

ok 1 number(s): "175789713405292"

Test #23:

score: 0
Accepted
time: 79ms
memory: 39464kb

input:

351493
697337673 266522793 679080819 687432689 315959590 268236149 622432001 129168391 88821388 63460774 833956640 413225945 865578649 11740512 786453528 891490067 227393189 334925606 170461981 87131025 281424141 946670090 604404324 925017592 888575931 471618837 629432076 743503791 324979198 8629246...

output:

175724312347028

result:

ok 1 number(s): "175724312347028"

Test #24:

score: 0
Accepted
time: 91ms
memory: 38136kb

input:

351493
9531759 599942847 513281388 9882449 796417077 291041867 324675328 353930252 412321421 947586559 980567086 932827768 615572841 156171760 286692109 886990028 854036272 728463778 206412416 607769313 369514800 628501404 675176090 546072905 149647950 881372300 854487923 790989321 278143384 9314385...

output:

176060086769570

result:

ok 1 number(s): "176060086769570"

Test #25:

score: 0
Accepted
time: 35ms
memory: 42296kb

input:

351493
643775169 784877155 491694248 460219180 421128561 836782766 473863207 74882458 186014002 171438888 487180871 816794740 59414460 519426472 148886585 918349979 15159789 599907429 955714969 506035160 720124140 982522735 4982763 971414716 606296383 279256990 561146067 112502530 687865897 90245951...

output:

175648851969743

result:

ok 1 number(s): "175648851969743"

Test #26:

score: 0
Accepted
time: 78ms
memory: 41584kb

input:

351493
123237838 283456533 538135616 244437927 706620575 310122605 992938749 472163222 432235898 484245342 707496878 494795908 169710548 623933631 26633626 961248631 718394700 717089363 9197104 187450047 894757617 248877232 996630094 315805422 595658941 572547722 304120890 318645450 136013835 705343...

output:

176082772867468

result:

ok 1 number(s): "176082772867468"

Test #27:

score: 0
Accepted
time: 86ms
memory: 41520kb

input:

351493
493928676 984704906 762295072 154664431 387000499 896160744 324405265 308004744 146928584 286540247 476051634 29387846 153694128 904411262 235634769 90897616 716372605 164062799 287383600 987535709 912413555 578718041 845850944 780667717 349187025 181006164 269798770 457360038 11494473 586660...

output:

175982434649427

result:

ok 1 number(s): "175982434649427"

Test #28:

score: 0
Accepted
time: 105ms
memory: 40248kb

input:

351493
373358965 951308820 424481180 333184243 762747734 299885513 496753597 384905589 952388078 213620815 278496250 26390625 340233798 679563691 954378041 269675534 688200374 328300513 630660987 729017309 708106475 394616923 85958853 207679917 920694818 428823833 200109332 105757527 672789240 17044...

output:

175523574288506

result:

ok 1 number(s): "175523574288506"

Test #29:

score: 0
Accepted
time: 42ms
memory: 42296kb

input:

351493
506414637 19246988 476208040 321308506 350947555 498933784 814387431 524390797 694368970 992574521 392132519 681977993 617740744 398570047 955429187 794467660 445101459 899280020 672979531 62822811 91114630 397022041 36970950 413181439 297515602 132779417 715324259 85542261 118543552 62088701...

output:

175964348079203

result:

ok 1 number(s): "175964348079203"

Test #30:

score: 0
Accepted
time: 91ms
memory: 41584kb

input:

351493
198986773 906039921 401561964 93692787 563587809 277069277 678358946 609472935 100076981 910544643 304070724 326539759 555008482 797065754 463351941 521204940 580755165 70283699 968677479 678670254 461445625 53081211 818350939 282327778 123198870 873506 986227805 684460826 703461192 383879044...

output:

175742703185211

result:

ok 1 number(s): "175742703185211"

Test #31:

score: 0
Accepted
time: 85ms
memory: 41600kb

input:

351493
80155259 677489804 317709905 738646332 926916041 417796814 406341624 483755769 292807023 179580462 793077212 266345199 545969570 486044911 715470803 444124568 31002634 985463900 389193993 592838646 861091277 63490585 660350533 828216029 427234331 20581790 342489221 996887734 917735536 8984175...

output:

176015004295927

result:

ok 1 number(s): "176015004295927"

Test #32:

score: 0
Accepted
time: 92ms
memory: 40456kb

input:

351493
502158417 129819235 891767970 99219238 183211216 247517042 540523173 223127548 890246367 488281842 142446217 419214467 64348530 964962625 160502713 368547515 849639720 446159538 419790713 352578054 409914263 635929477 175211453 71785060 341607425 623960228 540374304 235478238 941333686 405860...

output:

175933407600618

result:

ok 1 number(s): "175933407600618"

Test #33:

score: 0
Accepted
time: 51ms
memory: 42228kb

input:

351493
398441962 739520539 491612719 742311876 374717677 206652911 205850479 766243471 807089323 737974241 255255614 662249856 427102454 708382982 50385340 588046648 257468479 272568562 823245583 37260800 566193872 806916151 739940499 741176228 282055372 245646403 597782839 681382879 988980236 56915...

output:

175770971030507

result:

ok 1 number(s): "175770971030507"

Test #34:

score: 0
Accepted
time: 81ms
memory: 41532kb

input:

351493
880628558 121299849 543626556 62033726 562477905 807001043 375706344 218418912 907912385 670274061 135077427 922954507 32404993 210176781 996211632 619526575 919287588 729593055 761653998 610447247 809155528 512214275 521742984 864589741 530033320 679020122 655547772 939779173 682018784 71763...

output:

175730808311141

result:

ok 1 number(s): "175730808311141"

Test #35:

score: 0
Accepted
time: 76ms
memory: 41604kb

input:

351493
648831108 530007650 638538805 608006345 296077170 329899021 678769314 440482296 786721906 668042529 665202240 65800140 350709681 770903722 132697538 767023695 734488378 823129781 81049058 17970450 369322341 159217770 161299857 770481561 200199260 666640973 804754414 446866493 126946712 153790...

output:

175403445299245

result:

ok 1 number(s): "175403445299245"

Test #36:

score: 0
Accepted
time: 88ms
memory: 40408kb

input:

351493
502044059 501804302 211313768 511242 940995264 692839783 506574553 788353346 414910991 728892560 163315468 703340870 64162305 265589155 728350156 90806809 279802465 603050289 583538947 889537982 296696464 894996691 664404573 517096711 643986848 746421610 511916825 917579434 354474598 16810987...

output:

175704819099603

result:

ok 1 number(s): "175704819099603"

Test #37:

score: 0
Accepted
time: 46ms
memory: 40228kb

input:

351493
928817795 15279764 129664762 227080241 523789462 737285062 435944240 506893816 48628908 163684964 26567120 773587005 417584420 284427030 541080558 551027755 533540940 323802299 559241453 839256263 519627534 412275450 563331642 815778319 614934015 836399328 769156966 589297693 908680090 798560...

output:

175889450274061

result:

ok 1 number(s): "175889450274061"

Test #38:

score: 0
Accepted
time: 77ms
memory: 41656kb

input:

351493
251823026 589762742 883250226 961879394 735612675 902451776 40728364 60794721 55273426 161191483 59454831 807594742 528956045 913984188 24433970 559087551 115859648 526548286 32135802 697916215 58068040 394191777 509967320 883927969 307425399 597909709 568479829 932237308 679211452 562575518 ...

output:

175666089806924

result:

ok 1 number(s): "175666089806924"

Test #39:

score: 0
Accepted
time: 76ms
memory: 41656kb

input:

351493
985558020 54549874 730558353 134850543 426343132 553651399 98142769 39888642 60620869 919884891 642437383 798573040 753253917 962593094 378736236 977464159 307193246 831091882 406048067 858980717 316565234 586557313 893832302 589087976 295813039 297530468 815341048 84460051 664360694 54719444...

output:

175692300229036

result:

ok 1 number(s): "175692300229036"

Test #40:

score: 0
Accepted
time: 80ms
memory: 40124kb

input:

351493
795244249 805155169 525778916 836974679 299806591 692112605 622788823 43709098 172248498 161804880 803887069 398609832 320064475 776199168 867218919 146403854 81784201 663602929 874781937 276829658 612886854 545957546 753834680 356435736 62451554 626249096 280389459 216467831 587882687 849844...

output:

175668620388263

result:

ok 1 number(s): "175668620388263"

Subtask #3:

score: 0
Wrong Answer

Test #41:

score: 0
Wrong Answer
time: 3ms
memory: 16268kb

input:

7
247522519 398923496 -976223527 806215585 -937536479 -130552271 90576461
1 2 1 2 5 5

output:

3406397416

result:

wrong answer 1st numbers differ - expected: '3587550338', found: '3406397416'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%