QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#123066#4406. 独立集问题ezoilearner19 50ms49396kbC++141.9kb2023-07-11 17:56:342023-07-11 17:56:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-11 17:56:35]
  • 评测
  • 测评结果:19
  • 用时:50ms
  • 内存:49396kb
  • [2023-07-11 17:56:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define cout cerr
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)

typedef long long ll;
typedef pair<int,int> pii;
#define FR first
#define SE second
const ll inf=1e18;

inline void rd(int &x){
    x=0;char ch=getchar();int f=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    x*=f;
}
//是否解决 系数 类型

int n;
#define Maxn 400010
int a[Maxn];
int head[Maxn],v[Maxn],nxt[Maxn],tot=0;
void add_edge(int s,int e){
    tot++;v[tot]=e;nxt[tot]=head[s];head[s]=tot;
}
/*ll F[Maxn][8];

int calc(int a,int b){
    int a1=(a/2)&1,a2=a/4;
    int b1=(b/2)&1,b2=b/4;
    if(a2==1&&b2==1)return -1;
    if(a2==0&&b2==0)return 0;
    if(a2==0&&b2==1&&a1!=b1)return 1;
    if(a2==1&&b2==0&&a1!=b1)return 2;
    return 0;
}

ll fjz[8];*/
ll F[Maxn][4];
void dfs(int u){
    F[u][0]=0;F[u][1]=-inf;F[u][2]=a[u];F[u][3]=-a[u];
    ll s0=0,s1=0,s3=0;
    for(int i=head[u];i;i=nxt[i]){
        int t=v[i];
        dfs(t);
        ll z1=max(F[u][1]+max(F[t][2],F[t][3]),s3+max(F[t][2]-a[u],F[t][3]+a[u]));
        ll z3=s0+max(F[t][2]-a[u],F[t][3]+a[u]),z2=s1+max(F[t][2]-a[u],F[t][3]+a[u]);
        z1=max(z1,F[u][1]+F[t][1]);
        z2=max(z2,max(F[u][2]-a[t]+F[t][0],F[u][2]+F[t][1]));
        z3=max(z3,max(F[u][3]+a[t]+F[t][0],F[u][3]+F[t][1]));
        ll cur=max(F[t][3],max(F[t][1],F[t][2]));
        s0+=max(a[t]+F[t][0],cur);
        s1+=max(-a[t]+F[t][0],cur);s3+=cur;
        F[u][0]=max(s0,s1);
        F[u][1]=z1;F[u][2]=z2;F[u][3]=z3;
    }
}

int main(){
    rd(n);
    rep(i,1,n)rd(a[i]);
    rep(i,2,n){
        int x;rd(x);add_edge(x,i);
    }
    dfs(1);
    printf("%lld\n",max(F[1][3],max(F[1][1],F[1][2])));
    return 0;
}  

詳細信息

Subtask #1:

score: 13
Accepted

Test #1:

score: 13
Accepted
time: 23ms
memory: 47700kb

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:

175477002777567

result:

ok 1 number(s): "175477002777567"

Test #2:

score: 0
Accepted
time: 19ms
memory: 48764kb

input:

351493
-56100243 368534199 129964394 -89815018 -91235204 957523014 -460852634 -325788014 -402912154 321855921 454630730 558766063 227409254 -961488779 421605421 691666242 -230378151 -162955273 -236886327 -612720805 897977225 -86952503 798514303 108426380 652820044 -570978053 -646910035 -167973689 -7...

output:

175582921565606

result:

ok 1 number(s): "175582921565606"

Test #3:

score: 0
Accepted
time: 31ms
memory: 47896kb

input:

351493
763351894 914829770 269353066 -650659200 -281614670 -384638266 266301720 599060286 929263636 -383459829 900862182 -735284265 -207058691 -896484301 821480927 90661512 -679895618 -995726473 511471086 669880712 461077012 -131405343 997734902 -904033660 245840121 355028008 -909036951 530267463 93...

output:

175928061618383

result:

ok 1 number(s): "175928061618383"

Test #4:

score: 0
Accepted
time: 34ms
memory: 48608kb

input:

351493
-476871284 310380923 -524195986 740923407 -507205286 -708342444 845300375 163395319 -118327194 -777909892 -864449914 19995101 -709759263 -967727722 922294345 -493915772 -812562398 -365413759 787107009 4270638 -295451830 -162056816 -884264923 -870042647 -996069213 573972294 155864269 -58906286...

output:

175650564210340

result:

ok 1 number(s): "175650564210340"

Test #5:

score: 0
Accepted
time: 29ms
memory: 47708kb

input:

351493
-173531743 557238083 -824113374 -84997552 -528741973 -448737148 -646930897 649003342 -608133665 912285973 -922564290 602546534 116884217 -500565119 526827675 123739579 41774236 205999423 15304413 861611850 39040664 895088899 43155838 -326769005 671029213 124031672 249778755 -644568506 9118445...

output:

175833127330368

result:

ok 1 number(s): "175833127330368"

Test #6:

score: 0
Accepted
time: 29ms
memory: 48392kb

input:

351493
867082022 -654438792 -563132739 -602771213 -498674813 -925363988 -32298673 -538019554 -334530735 571873145 -583030757 -378539176 119681995 -90196121 460241188 -516789360 211603768 -509897029 -852347880 830444888 269349329 -428858753 -137073395 130042891 644002528 -137140981 979900884 36818325...

output:

175483737223472

result:

ok 1 number(s): "175483737223472"

Test #7:

score: 0
Accepted
time: 20ms
memory: 48600kb

input:

351493
-447335302 -476762578 372057221 936789657 357038272 909731828 -683347165 637447470 913095563 316451704 414765801 786600053 -65647567 924518593 -769778430 -347838583 923771357 54765382 355559903 -210849764 194278668 612466423 120679972 -184875188 -467919689 -45407455 -881561838 -591488257 2692...

output:

175817072416071

result:

ok 1 number(s): "175817072416071"

Test #8:

score: 0
Accepted
time: 32ms
memory: 48816kb

input:

351493
402240742 668233786 -889881161 457723983 862248981 -258221456 961999793 -357283684 -906564302 -597314876 739970397 -677435760 -950807663 -637315042 -933332320 277627831 540469730 711450896 -516333572 663145310 104913901 -511477049 703469693 -593297236 -407591592 804894830 504458817 -220727610...

output:

175806964829997

result:

ok 1 number(s): "175806964829997"

Test #9:

score: 0
Accepted
time: 33ms
memory: 48356kb

input:

351493
76730680 435846940 -794852623 555620609 -611204625 838568963 -703848513 -448239085 -115097249 -41368701 370845103 -523596605 -574028136 -999717105 -940170307 -882957379 168314209 462026163 -596102197 223187871 -231867307 165204442 -217815785 982666489 616325768 -834213481 -7172241 587603787 9...

output:

175645279435054

result:

ok 1 number(s): "175645279435054"

Test #10:

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

input:

351493
-418521650 -556841193 201271611 -455552220 660456263 -188352499 400020859 986402784 -477116947 -886627587 -840995307 438113972 -154696898 -817068532 -876194676 -576445413 -955919626 -10695871 313744268 -647421383 -836372934 -41870379 -384156565 570580595 136462961 602569688 644933476 52733996...

output:

175802261388786

result:

ok 1 number(s): "175802261388786"

Test #11:

score: 0
Accepted
time: 23ms
memory: 48248kb

input:

351493
-130691318 904648843 -732528532 646985259 8633249 -936982284 497541179 640396747 650407531 458099270 -690004072 889148550 -350891786 120609938 -210082522 -729055455 -507136771 754502959 742704465 -771332127 41517881 815637674 193201716 -748352958 816227236 8740519 661093724 -269939318 7725096...

output:

175701865379333

result:

ok 1 number(s): "175701865379333"

Test #12:

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

input:

351493
-66854912 -950343871 -199904682 509621680 495040850 929289473 158195385 24793111 617279847 -851601360 -376102480 -28253220 526524472 165842584 -938843661 -255803056 427156408 -921301927 -493038885 -301127735 -392384028 -897791614 -404752254 -331044497 640039210 -718591427 -655295253 -78657017...

output:

175609650615928

result:

ok 1 number(s): "175609650615928"

Test #13:

score: 0
Accepted
time: 20ms
memory: 48056kb

input:

351493
78301096 -52604596 821967420 17665215 -854562351 531797012 531579374 -630259969 483552256 -406544826 -444229744 -36337606 -923613351 572356707 150744251 -893122680 -867494723 -787026829 -57721719 854240591 -997955163 -521393917 -601344208 428938884 -361341200 -930370842 511195865 657470791 -9...

output:

175839770381205

result:

ok 1 number(s): "175839770381205"

Test #14:

score: 0
Accepted
time: 30ms
memory: 49396kb

input:

351493
-386682919 -77525384 946023467 359887410 608228613 -61098422 -221702696 677632268 -464778216 -208646176 376278620 -174464731 -71286142 545647495 775301975 360115639 210057946 930655420 -285693349 264575602 -205129496 148376086 -723599206 671466170 -516424717 -456455162 -412650777 -833372579 -...

output:

175710205504618

result:

ok 1 number(s): "175710205504618"

Test #15:

score: 0
Accepted
time: 32ms
memory: 49124kb

input:

351493
180349695 744582170 -231466196 311156193 -918224163 742801932 499244357 -122245208 -945991826 632811907 -702788218 -377450924 -127055866 413899582 377349215 -109237274 875498449 984669327 -582590434 -535969194 -515202930 -865614356 712340219 -432417784 -259839200 -334614797 629153456 45235977...

output:

176087255650160

result:

ok 1 number(s): "176087255650160"

Test #16:

score: 0
Accepted
time: 18ms
memory: 48468kb

input:

351493
109291948 656740495 -240687300 816865496 842030537 -83872038 945788784 -175127748 -220378521 -514168111 -75918273 -424031742 618185653 -425893462 184086440 246901383 84933177 484058459 -92426164 41491205 -322743318 -110098421 870843057 441185062 -905737330 -905272154 -954353925 -645539990 -87...

output:

175519371658187

result:

ok 1 number(s): "175519371658187"

Test #17:

score: 0
Accepted
time: 22ms
memory: 48432kb

input:

351493
-614599670 -474846006 -710707577 106808435 -164026900 -724701218 -303848501 558316928 270492819 282023076 -782348251 -886449416 984530125 -357437687 258764323 418885593 479670569 -80377126 754298657 812349532 -410328644 665455088 -524573843 -608180507 987618127 -953474049 -639822420 14005562 ...

output:

175786283410751

result:

ok 1 number(s): "175786283410751"

Test #18:

score: 0
Accepted
time: 30ms
memory: 48436kb

input:

351493
313622497 -362940646 -140097326 256552576 724046027 -409629799 414191927 -893521269 468491250 -617455748 586032127 119415071 378904243 351070874 -986532004 663803846 -866585240 954006674 -955305655 -448803947 621831295 865445237 -543156005 611055742 23286086 343559876 921703921 149690983 -586...

output:

175515918477177

result:

ok 1 number(s): "175515918477177"

Test #19:

score: 0
Accepted
time: 25ms
memory: 48532kb

input:

351493
210604902 501648292 658492051 -525347627 -355907514 215124219 -86804060 996495834 -188590493 -641319941 -220244419 141195062 806233339 -318366404 25549101 -172002820 -797770181 670028866 734746879 -815883678 -641475613 796222600 407452159 -634832863 500778632 640126487 -119988287 294492816 75...

output:

175726295662131

result:

ok 1 number(s): "175726295662131"

Test #20:

score: 0
Accepted
time: 40ms
memory: 48996kb

input:

351493
-843129055 -348494677 -733126523 -699082751 -414986184 -488503685 -801447831 826403161 -690681531 -978669772 -100314374 -11538509 -697056616 719592518 511215252 -522716064 535232416 91782539 739147694 -280251272 -529888836 942685287 861536350 331302306 782848263 648864506 -945194734 -20036503...

output:

175405997725361

result:

ok 1 number(s): "175405997725361"

Subtask #2:

score: 6
Accepted

Test #21:

score: 6
Accepted
time: 8ms
memory: 22264kb

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: 25ms
memory: 20344kb

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: 37ms
memory: 21324kb

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: 36ms
memory: 21800kb

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: 12ms
memory: 21984kb

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: 38ms
memory: 20972kb

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: 34ms
memory: 20716kb

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: 37ms
memory: 21268kb

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: 35ms
memory: 22328kb

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: 29ms
memory: 20244kb

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: 46ms
memory: 21272kb

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: 44ms
memory: 21564kb

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: 27ms
memory: 22576kb

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: 38ms
memory: 21384kb

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: 41ms
memory: 21304kb

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: 37ms
memory: 21284kb

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: 18ms
memory: 22344kb

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: 38ms
memory: 21716kb

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: 28ms
memory: 20372kb

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: 50ms
memory: 21040kb

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: 11
Accepted
time: 1ms
memory: 7620kb

input:

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

output:

3587550338

result:

ok 1 number(s): "3587550338"

Test #42:

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

input:

7
-822791105 523257970 894601243 -90617653 -41818991 -868075494 -944374389
1 2 3 3 5 2

output:

4185536845

result:

ok 1 number(s): "4185536845"

Test #43:

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

input:

7
-566350725 996649344 340685939 565531548 -379550593 -183515822 -6548810
1 2 3 4 5 6

output:

3038832781

result:

ok 1 number(s): "3038832781"

Test #44:

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

input:

7
-343171001 -403362511 46959184 -369697450 -102687963 -567117121 955599726
1 1 2 4 4 4

output:

2788594956

result:

ok 1 number(s): "2788594956"

Test #45:

score: 0
Accepted
time: 2ms
memory: 7660kb

input:

7
173828143 336914236 941275489 295810310 -887412118 -714471730 -912582442
1 2 1 1 2 2

output:

4262294468

result:

ok 1 number(s): "4262294468"

Test #46:

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

input:

7
-572833222 21134507 42426361 861990387 -480811920 230941373 544927922
1 2 3 3 5 6

output:

2755065692

result:

ok 1 number(s): "2755065692"

Test #47:

score: -11
Wrong Answer
time: 1ms
memory: 7836kb

input:

7
-680443605 -209348563 840970142 -137922464 901658290 459523902 264391423
1 1 1 1 3 4

output:

3075561263

result:

wrong answer 1st numbers differ - expected: '3494258389', found: '3075561263'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%