QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#326686#6298. ColoringC1942huangjiaxuWA 38ms199748kbC++14947b2024-02-13 18:35:332024-02-13 18:35:34

Judging History

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

  • [2024-02-13 18:35:34]
  • 评测
  • 测评结果:WA
  • 用时:38ms
  • 内存:199748kb
  • [2024-02-13 18:35:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
typedef long long ll;
vector<int>e[N];
int n,s,o,a[N],w[N],p[N],rg[N],cr,c[N];
ll f[N][N],ans,sum;
bool vis[N];
void dfs(int x){
	for(int i=1;i<=n;++i)f[x][i]=-1ll*p[x]*i+(i&1)*w[x];
	for(auto v:e[x])if(!vis[v]){
		dfs(v);
		ll mx=0;
		for(int j=1;j<=n;++j){
			mx=max(mx,f[v][j]);
			f[x][j]+=mx;
		}
	}
}
int main(){
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;++i)scanf("%d",&w[i]);
	for(int i=1;i<=n;++i)scanf("%d",&p[i]);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		e[a[i]].push_back(i);
	}
	for(o=s;!vis[o];o=a[o])vis[o]=true,rg[++cr]=o;
	if(o!=s){
		dfs(s);
		printf("%lld\n",max(f[s][1],f[s][2])+p[s]);
		return 0;
	}
	for(int i=1;i<=cr;++i)dfs(rg[i]);
	for(int i=1;;--i){
		if(!i)i=cr;
		int x=rg[i];
		sum-=f[x][c[x]];
		++c[x];
		if(c[x]>n)break;
		sum+=f[x][c[x]];
		ans=max(ans,sum+p[s]);
	}
	printf("%lld\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0ms
memory: 3980kb

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: 4ms
memory: 197024kb

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: -100
Wrong Answer
time: 38ms
memory: 199748kb

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:

692335671638

result:

wrong answer 1st numbers differ - expected: '484763000532', found: '692335671638'