QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#625946 | #4406. 独立集问题 | Kevin5307 | 13 | 75ms | 85996kb | C++23 | 1.8kb | 2024-10-09 21:58:50 | 2024-10-09 21:58:51 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
ll d[500500];
int p[500500],n;
vector<int> G[500500];
ll f[500500][2][2][2];
void dfs(int u)
{
for(auto v:G[u])
dfs(v);
for(int st=0;st<2;st++)
{
ll tmp[2]={0,-1ll*inf*inf};
for(auto v:G[u])
{
ll w1=max(f[v][0][st][1]-d[u],f[v][1][st][1]+d[u]);
ll w0=0;
for(int a=0;a<2;a++)
for(int b=0;b<2;b++)
w0=max(w0,f[v][a][st][b]);
tmp[1]=max(tmp[1]+w0,tmp[0]+w1);
tmp[0]+=w0;
}
for(int a=0;a<2;a++)
for(int b=0;b<2;b++)
{
ll ntmp[2]={tmp[0],tmp[1]};
if(!b)
{
ll w0=0;
ll w1=(a?d[u]:-d[u]);
tmp[1]=max(tmp[1]+w0,tmp[0]+w1);
tmp[0]+=w0;
}
f[u][st][a][b]=tmp[1];
}
ll tot=0;
for(auto v:G[u])
tot+=max(f[v][0][st][0],f[v][1][st][0]);
tot+=(st?-d[u]:d[u]);
for(int a=0;a<2;a++)
f[u][st][a][1]=max(f[u][st][a][1],tot);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>d[i];
for(int i=2;i<=n;i++)
cin>>p[i];
for(int i=2;i<=n;i++)
G[p[i]].pb(i);
dfs(1);
cout<<max(f[1][0][0][1],f[1][1][0][1])<<'\n';
return 0;
}
詳細信息
Subtask #1:
score: 13
Accepted
Test #1:
score: 13
Accepted
time: 58ms
memory: 85996kb
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: 13
Accepted
time: 65ms
memory: 85292kb
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: 13
Accepted
time: 64ms
memory: 85032kb
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: 13
Accepted
time: 47ms
memory: 85080kb
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: 13
Accepted
time: 58ms
memory: 85616kb
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: 13
Accepted
time: 69ms
memory: 85288kb
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: 13
Accepted
time: 75ms
memory: 85392kb
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: 13
Accepted
time: 53ms
memory: 85108kb
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: 13
Accepted
time: 55ms
memory: 83056kb
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: 13
Accepted
time: 50ms
memory: 83048kb
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: 13
Accepted
time: 56ms
memory: 85108kb
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: 13
Accepted
time: 57ms
memory: 83036kb
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: 13
Accepted
time: 51ms
memory: 85168kb
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: 13
Accepted
time: 71ms
memory: 85936kb
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: 13
Accepted
time: 63ms
memory: 85652kb
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: 13
Accepted
time: 62ms
memory: 85092kb
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: 13
Accepted
time: 65ms
memory: 85392kb
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: 13
Accepted
time: 55ms
memory: 84220kb
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: 13
Accepted
time: 62ms
memory: 85648kb
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: 13
Accepted
time: 49ms
memory: 85136kb
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: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 70ms
memory: 49876kb
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:
175766699901644
result:
wrong answer 1st numbers differ - expected: '175766699890054', found: '175766699901644'
Subtask #3:
score: 0
Wrong Answer
Test #41:
score: 11
Accepted
time: 2ms
memory: 7664kb
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: 11
Accepted
time: 0ms
memory: 7724kb
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: 11
Accepted
time: 2ms
memory: 7788kb
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: 11
Accepted
time: 2ms
memory: 7676kb
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: 11
Accepted
time: 2ms
memory: 7724kb
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: 11
Accepted
time: 2ms
memory: 7808kb
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
Accepted
time: 2ms
memory: 7664kb
input:
7 -680443605 -209348563 840970142 -137922464 901658290 459523902 264391423 1 1 1 1 3 4
output:
3494258389
result:
ok 1 number(s): "3494258389"
Test #48:
score: 11
Accepted
time: 2ms
memory: 7724kb
input:
7 894515913 -285833848 200232559 -124848987 -155423899 -388397871 -738157137 1 2 1 3 4 1
output:
2787410214
result:
ok 1 number(s): "2787410214"
Test #49:
score: 11
Accepted
time: 0ms
memory: 7784kb
input:
7 -642380669 158308062 -127045342 711767901 -181174983 -826955836 -244494777 1 1 2 2 2 3
output:
2892127570
result:
ok 1 number(s): "2892127570"
Test #50:
score: 11
Accepted
time: 2ms
memory: 7784kb
input:
7 -449719640 653672153 -305651153 -120669406 801070860 856021669 75279964 1 2 3 4 5 1
output:
3262084845
result:
ok 1 number(s): "3262084845"
Test #51:
score: 11
Accepted
time: 0ms
memory: 7668kb
input:
7 -33901197 115600154 -335654692 -679018907 458398904 149062361 -984194456 1 2 2 4 3 1
output:
2755830671
result:
ok 1 number(s): "2755830671"
Test #52:
score: 0
Wrong Answer
time: 2ms
memory: 7748kb
input:
7 516920012 53907302 586206756 495875317 -54807878 -985037423 -764269876 1 1 2 2 2 5
output:
3457024564
result:
wrong answer 1st numbers differ - expected: '3347408808', found: '3457024564'
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:
0%