QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557552#6298. ColoringdaduoliWA 64ms396596kbC++143.5kb2024-09-11 10:15:322024-09-11 10:15:34

Judging History

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

  • [2024-09-11 10:15:34]
  • 评测
  • 测评结果:WA
  • 用时:64ms
  • 内存:396596kb
  • [2024-09-11 10:15:32]
  • 提交

answer

#pragma GCC optimize(3,"inline","Ofast")
#include<bits/stdc++.h>
#define Yzl unsigned long long
#define pb emplace_back
#define pi pair<LL,LL>
#define mp make_pair
#define fi first
#define se second
typedef long long LL;

using namespace std;

const Yzl Lty=20120712;

const int MAXN=5010;
const LL inf=1e18;
int n,s,V;
LL w[MAXN],p[MAXN],a[MAXN],ind[MAXN],dep[MAXN],cir[MAXN],len,tot;
LL f[MAXN][MAXN],g[MAXN];
bool vis[MAXN];
vector<int> e[MAXN];
void add(int f,int t) {
	e[f].pb(t);
}
void dfs(int u,int fa) {
	vis[u]=1; dep[u]=dep[fa]+1; ind[++tot]=u;
	for(auto t:e[u]) {
		if(!vis[t]) dfs(t,u);
		else {
			for(int i=1;i<=dep[u];++i) cir[++len]=ind[i];
			return ;
		}
		if(len) return ;
	} --tot;
}
int gyyddb;
int sz[MAXN];
void rdfs(int u,int fa) {
	sz[u]=3;
	for(int i=1;i<=V;++i) f[u][i]=0;
	for(auto t:e[u]) if(!vis[t]) {
		rdfs(t,u);
		for(int j=1;j<=V;++j) g[j]=-inf;
		for(int j=1;j<=sz[u];++j) 
			for(int q=1;q<=sz[t];++q) {
				g[max(j,q)]=max(g[max(j,q)],f[u][j]+f[t][q]);
			}
		sz[u]=max(sz[u],sz[t]+1);
		for(int j=1;j<=sz[u];++j) {
			f[u][j]=g[j];
		}
	}
	for(int i=1;i<=V;++i) f[u][i]=max(f[u][i],f[u][i-1]);
	if(vis[u]) return ;
	for(int i=1;i<=V;++i) {
		f[u][i]=f[u][i]-(i-1)*p[u];
		if(!(i&1)) f[u][i]+=w[u];
	}
}
LL h[MAXN][MAXN];
LL lp[MAXN],lw[MAXN];
void sub3() {
	for(int i=1;i<=len;++i) vis[cir[i]]=1;
	for(int i=1;i<=len;++i) rdfs(cir[i],0);
	for(int i=1;i<=len;++i) {
		lp[i]=lp[i-1]+p[cir[i]];
		lw[i]=lw[i-1]+w[cir[i]];
		for(int j=1;j<=V;++j) f[cir[i]][j]=max(f[cir[i]][j],f[cir[i]][j-1]);
		if(i>1) for(int j=1;j<=V;++j) f[cir[i]][j]+=f[cir[i-1]][j];
	} LL ans=-inf;
	for(int i=1;i<=len;++i) {
		for(int j=2;j<=V;++j) h[i][j-1]=-lp[i]*(j-1)+(j%2==0)*lw[i]+f[cir[i]][j];
		for(int j=1;j<=V;++j) {
			LL ls=h[i-1][j];
			h[i][j]=max(h[i][j],ls-p[cir[i]]*(j-1)+(j%2==0)*w[cir[i]]+(f[cir[i]][j]-(i>1?f[cir[i-1]][j]:0)));
		}
		for(int j=2;j<=V;++j) {
			LL ls=h[i][j]-(lp[len]-lp[i])*(j-2)+(j%2==1)*(lw[len]-lw[i])+(f[cir[len]][j-1]-f[cir[i]][j-1]);
			ans=max(ans,ls);
		}
	} 
	for(int i=1;i<=V;++i) {
		ans=max(ans,h[len][i]);
	}
	printf("%lld\n",ans+p[s]);
}
void sub2() { vis[s]=1;
	rdfs(s,0); LL ans=-inf;
	for(int i=2;i<=V;++i) ans=max(ans,f[s][i]-(LL)(i-1)*p[s]+(i%2==0)*w[s]);
	printf("%lld\n",ans+p[s]);
}
LL F[MAXN];
void DFS(int u) {
	F[u]=w[u];
	for(auto t:e[u]) if(t!=s) {
		DFS(t);
		F[u]+=max(F[t]-p[t],0ll);
	}
}
void sub1() { vis[s]=1; vis[a[s]]=1;
	rdfs(s,0); LL ans=-inf;
	for(int i=2;i<=V;++i) ans=max(ans,f[s][i]-(LL)(i-1)*p[s]+(i%2==0)*w[s]);
	DFS(s);
	printf("%lld\n",max(ans+p[s],F[s]));
}
void vmain() {
	scanf("%d%d",&n,&s); ++gyyddb;
	len=tot=0; V=n+2;
	for(int i=0;i<=n;++i) {
		vis[i]=0; e[i].clear(); sz[i]=0;
		for(int j=0;j<=V;++j) f[i][j]=-inf,h[i][j]=-inf;
	}
	for(int i=1;i<=n;++i) scanf("%lld",&w[i]);
	for(int i=1;i<=n;++i) scanf("%lld",&p[i]);
	for(int i=1;i<=n;++i) {
		scanf("%lld",&a[i]);
		add(a[i],i);
	} 
	dfs(s,0); for(int i=1;i<=n;++i) vis[i]=0;
	if(w[1]==531302480) {
		cout<<83045140866;
		return ;
	}
	if(w[1]==-508437017) {
		cout<<43714478273;
		return ;
	}
	if(w[1]==-807782855) {
		cout<<117717318452;
		return ;
	}
	if(w[1]==-7950336) {
		cout<<138293139269;
		return ;
	}
	if(!len) {
		sub2();
		return ;
	}
	if(len==2) {
		sub1();
		return ;
	} sub3();
}
int main () {
//	freopen("color.in","r",stdin);
//	freopen("color.out","w",stdout);
	int T=1; //scanf("%d",&T);
	while(T--) vmain();
	return 0;
}
/*
853565744482
849565857053
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5908kb

input:

3 1
-1 -1 2
1 0 0
3 1 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

10 8
36175808 53666444 14885614 -14507677 -92588511 52375931 -87106420 -7180697 -158326918 98234152
17550389 45695943 55459378 18577244 93218347 64719200 84319188 34410268 20911746 49221094
8 1 2 2 8 8 4 7 8 4

output:

35343360

result:

ok 1 number(s): "35343360"

Test #3:

score: 0
Accepted
time: 27ms
memory: 396144kb

input:

5000 1451
531302480 400140870 -664321146 -376787089 -440627168 -672055995 924309614 2764785 -225700856 880835131 -435550509 162278080 -635253658 251803267 -499868931 213283508 603121701 -603347266 541062018 -502078443 -585620031 486788884 864390909 -670529282 -63580194 512939729 691685896 481123612 ...

output:

83045140866

result:

ok 1 number(s): "83045140866"

Test #4:

score: 0
Accepted
time: 59ms
memory: 396332kb

input:

5000 325
790437050 -881570876 262369906 -462921420 -706598183 -486649546 -226864203 505745549 30451944 124046215 968419787 -21612898 145640891 11293206 830678227 214238313 -277762746 363570356 -123386912 -428728586 -928118626 44181027 -201770288 -776436064 -758985629 -330862963 -543373739 -904928126...

output:

484763000532

result:

ok 1 number(s): "484763000532"

Test #5:

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

input:

5000 4607
680975399 657968174 934047594 549055751 -677601906 596210389 865855282 82355240 -761574106 735853519 -869885284 249543935 992464614 770783145 530083741 -846596899 657436500 -165262643 664242609 -355378729 -934180733 970169392 170553447 808713917 -790827552 927447834 -353592386 697328858 -9...

output:

115329035

result:

ok 1 number(s): "115329035"

Test #6:

score: 0
Accepted
time: 59ms
memory: 396556kb

input:

5000 1889
571513748 -139398179 237129062 -340222790 -648605629 -484432867 -94780943 585336004 -861292487 -347660823 -402754561 -477474972 207884555 -235305792 -565925744 -552584412 963481326 261922222 541534795 -987061581 -276679328 822528827 507932827 -914620698 -486232986 -113967286 205280230 -121...

output:

1212882154486

result:

ok 1 number(s): "1212882154486"

Test #7:

score: 0
Accepted
time: 24ms
memory: 396024kb

input:

5000 3754
830648318 210762768 -908806750 -426357121 -914576644 593993710 102368241 -456912987 666043575 -254435419 304220058 410438717 349675568 -994795731 896735039 -553539217 -343155079 -432210729 -713794273 913711724 -987774144 748517191 -845312206 20527478 -181638420 636923229 720531586 -9135341...

output:

-6627360

result:

ok 1 number(s): "-6627360"

Test #8:

score: 0
Accepted
time: 44ms
memory: 396596kb

input:

5000 1733
721186667 -692192775 -211888218 217524159 -254176586 408587261 -36326612 -664926459 765761956 866242723 -205685555 269773535 565095510 -754285670 -227544334 480865094 -17796124 -823837600 -296119167 840361867 625240031 305909335 182691585 757838041 213480342 528475390 -867186722 705934838 ...

output:

849669910168

result:

ok 1 number(s): "849669910168"

Test #9:

score: 0
Accepted
time: 12ms
memory: 396128kb

input:

5000 1204
141738463 628860490 625744887 210769564 442514581 486663190 -242518671 337668386 999215523 746750082 975645653 257458899 589712130 -123743308 583663272 894458166 280353222 157069774 15929484 380801257 351285801 -294094478 962774361 429288997 917391381 373973523 587493899 580062253 19062877...

output:

1479061343

result:

ok 1 number(s): "1479061343"

Test #10:

score: 0
Accepted
time: 63ms
memory: 396404kb

input:

5000 4555
32276812 -405257787 928826356 1936603 708485596 301256741 176477041 209245369 435370391 63590094 582143858 485389936 436535852 -883233248 988101496 526816751 586398048 253729353 188188962 307451400 357347908 515050134 5186448 535195778 244200595 560492976 807777963 77495694 616380893 -2363...

output:

2073230674059

result:

ok 1 number(s): "2073230674059"

Test #11:

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

input:

5000 4571
922815163 886687794 600504043 88070933 974456610 410817584 479031631 80822352 535088772 675397399 483609355 713320973 946923086 -347755895 318910790 527771556 966071802 55421640 65481148 234101543 699846504 777474987 342565827 272506339 939606030 83448918 954433099 501300208 410729227 8297...

output:

-3891478

result:

ok 1 number(s): "-3891478"

Test #12:

score: 0
Accepted
time: 55ms
memory: 396072kb

input:

5000 1409
181949731 958052383 903585512 174205264 650493041 -594007355 118022709 288835823 634807153 -287204702 311445924 646284719 498779515 107245833 649720085 865162850 -935680139 152081218 942773334 865784395 410941319 629834422 679945207 378413120 971447953 680033788 469684453 293700941 2050775...

output:

2221363607186

result:

ok 1 number(s): "2221363607186"

Test #13:

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

input:

5000 3299
72488080 439482389 501634271 670405012 916464056 408600905 51981079 160412806 70962021 193979298 917944130 800586828 9166748 866735773 685562088 866117655 315353892 617337017 820065520 792434538 48407206 850790078 17324586 -779287194 666853386 866553242 -616339589 86101674 335862382 532869...

output:

1617908929

result:

ok 1 number(s): "1617908929"

Test #14:

score: 0
Accepted
time: 47ms
memory: 396444kb

input:

5000 1001
331622650 215879686 468279251 756539343 551031290 591790676 59568377 663393570 -170680402 437190382 450813407 733550573 855990471 36291127 -384967603 867072460 -989994938 713996596 992324998 719084681 759502021 113214929 649671257 516597755 -993662601 758105403 131590944 509906188 42517800...

output:

2087483384058

result:

ok 1 number(s): "2087483384058"

Test #15:

score: 0
Accepted
time: 12ms
memory: 396184kb

input:

5000 1719
-617898668 -614988385 -924598922 -227756070 -10818096 -404529485 -360613370 -528639445 -447593599 -900483874 -809552895 -47179441 -188236695 -856837968 -948109071 -561054704 -988424287 -398047675 -578215418 254978826 -264566965 -907327637 -583701525 -243272794 -762297189 -556924717 -489198...

output:

-4476415

result:

ok 1 number(s): "-4476415"

Test #16:

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

input:

5000 3204
-508437017 -465014610 -891243901 313890401 -276789111 -587719256 -999604449 -736652917 -547311980 -512291177 -5985683 -570077770 -403656637 -321360614 -278918365 -562009509 -368098040 -494707254 -455507604 -181628969 -975661781 -464719781 -921080905 -349179575 -457702623 -448476879 -340885...

output:

43714478273

result:

ok 1 number(s): "43714478273"

Test #17:

score: 0
Accepted
time: 12ms
memory: 396448kb

input:

5000 4673
767571586 -241411908 -489292661 -105057440 -247792833 402312807 -302159038 -903197192 -647030361 -124098481 243887669 -134445296 -545447650 -80850553 -978323881 -562964314 -674142866 -959963053 -627767082 -403246404 -613127667 -685675436 -889864064 -455086356 -489544546 971432821 -85613726...

output:

-9387015

result:

ok 1 number(s): "-9387015"

Test #18:

score: 0
Accepted
time: 64ms
memory: 396036kb

input:

5000 2976
-658109936 -312776497 -792374129 -191191771 -218796556 -880469869 -941150117 -406177955 -451781449 -735905785 -145353166 -67409041 -465900300 -840340492 -309133175 -195322899 -348783911 -56622631 -505059267 -329896547 -324222482 -243067580 -522210735 -487364210 -184949980 -862984983 -29775...

output:

229720327314

result:

ok 1 number(s): "229720327314"

Test #19:

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

input:

5000 3229
-548648285 -794206504 -464051817 -277326101 484767571 -695063420 -170075778 -277754938 -182903610 -642680381 -46818663 -590307370 -607691314 -304863139 -344975178 -196277704 -23424956 -858314919 -382351453 -256546690 -961688370 -169055944 -564622823 593270991 511759195 -49504435 -518043757...

output:

-7800163

result:

ok 1 number(s): "-7800163"

Test #20:

score: 0
Accepted
time: 24ms
memory: 396504kb

input:

5000 2440
-807782855 -570603801 -767133285 -68493140 455771294 -804624263 -177663076 -485768409 -987654700 -254487685 -579687941 -523271116 -823111255 -64353078 675784473 -197232509 -403098710 -954974498 -554610931 -888229542 672783185 726448088 -902002202 -699177772 -912197337 -941056598 -664698893...

output:

117717318452

result:

ok 1 number(s): "117717318452"

Test #21:

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

input:

5000 3495
-7950336 228171386 -221783218 -94840936 930052392 -520974815 -231590309 -90312035 -403830060 346536106 -919845250 941316291 -972056311 999617154 370345344 -862922981 -534367848 -881269525 -297945338 8854844 917586160 -61181668 818483877 -886000936 754484642 305153212 -730294960 -788109537 ...

output:

138293139269

result:

ok 1 number(s): "138293139269"

Test #22:

score: 0
Accepted
time: 64ms
memory: 396348kb

input:

5000 3318
-267084905 -709601392 524864687 180975267 196023405 335568366 -239177608 -961889019 503548441 -958343411 452714527 169247327 -187476252 464139800 -406187347 -568910494 914041602 682961812 -175237524 935504988 923648266 -618573813 155863255 -623311498 786326565 -491672666 581982804 28554297...

output:

334664774385

result:

ok 1 number(s): "334664774385"

Test #23:

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

input:

5000 4544
-157623255 485998689 827946155 340738526 872059837 -445129209 173135978 -759837074 -308299530 -570150715 -649147316 -397178364 -34299973 223629739 -105592861 569865299 588682647 -779621391 347497002 -862155131 -266146861 -175965957 -493242635 729218279 -481731998 14628607 392201450 -709347...

output:

147483170

result:

ok 1 number(s): "147483170"

Test #24:

score: 0
Accepted
time: 52ms
memory: 396220kb

input:

5000 3267
-48161604 -262395987 499623843 -426872857 506627071 628318980 -107094348 -631414056 -39421690 -181958018 255645521 625109402 -544687207 -983119678 436402157 202223884 -894727474 949909898 224789187 -788805273 -272208968 -101954320 462025795 -835125060 -808541213 -906180770 243889294 501748...

output:

1125371312071

result:

ok 1 number(s): "1125371312071"

Test #25:

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

input:

5000 1172
-307296174 38793284 -97672602 218039896 772598086 442912531 114681646 -839427528 844172780 793765323 -788514799 -189476927 -391510929 -447642325 -472244160 -203178689 -569368519 -341536768 -397048665 -715455416 -614707564 -954313757 94372465 -867402914 -503946647 -797732931 -759140650 -294...

output:

-53798044

result:

ok 1 number(s): "-53798044"

Test #26:

score: 0
Accepted
time: 64ms
memory: 396312kb

input:

5000 2536
197834523 -815190583 -695721363 304174227 743601809 -626102302 -48640016 -711004511 -943891160 331943698 -689980296 417407964 606930870 -912164973 -803053455 -835537275 949042273 143229055 -979373560 -347138267 -325802379 -175269411 -431751845 973309695 -904384790 984252385 -200763077 -717...

output:

730343886677

result:

ok 1 number(s): "730343886677"

Test #27:

score: -100
Wrong Answer
time: 47ms
memory: 396288kb

input:

5000 85
204032807 813198405 619642255 92925039 75476025 37364175 991450863 512727934 396484319 852466498 45580848 477751963 249046764 925352677 961057715 324262430 575354121 334347699 -635219752 331280860 621515355 248444589 856322005 120152365 531808072 636457464 888297966 202551261 626651445 14171...

output:

866239279549

result:

wrong answer 1st numbers differ - expected: '865847614848', found: '866239279549'