QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#326683#6298. ColoringC1942huangjiaxuWA 55ms199624kbC++14862b2024-02-13 18:31:502024-02-13 18:31:50

Judging History

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

  • [2024-02-13 18:31:50]
  • 评测
  • 测评结果:WA
  • 用时:55ms
  • 内存:199624kb
  • [2024-02-13 18:31:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
typedef long long ll;
vector<int>e[N];
int n,s,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(int i=s;!vis[i];i=a[i])vis[i]=true,rg[++cr]=i;
	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: 0ms
memory: 4024kb

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: 4036kb

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

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:

599586694040

result:

wrong answer 1st numbers differ - expected: '83045140866', found: '599586694040'