QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#359764#6298. ColoringzhouhuanyiWA 1ms4332kbC++231.2kb2024-03-20 20:42:432024-03-20 20:42:44

Judging History

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

  • [2024-03-20 20:42:44]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4332kb
  • [2024-03-20 20:42:43]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#define N 5000
using namespace std;
const long long inf=(long long)(1e18);
int read()
{
	char c=0;
	int sum=0,f=1;
	while (c!='-'&&(c<'0'||c>'9')) c=getchar();
	if (c=='-') c=getchar(),f=-1;
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum*f;
}
int n,s,w[N+1],p[N+1],fa[N+1],a[N+1];
long long dp[N+1][3],ans;
vector<int>E[N+1];
bool used[N+1];
void dfs(int x)
{
	long long res;
	for (int op=1;op<=2;++op) dp[x][op]=w[x]*(op==1)-p[x]*op;
	used[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
		{
			fa[E[x][i]]=x,dfs(E[x][i]);
			for (int op=1;op<=2;++op)
			{
				res=0;
				for (int opt=1;opt<=op;++opt) res=max(res,dp[E[x][i]][opt]);
				dp[x][op]+=res;
			}
		}
	return;
}
int main()
{
	vector<int>sp;
	n=read(),s=read();
	for (int i=1;i<=n;++i) w[i]=read();
	for (int i=1;i<=n;++i) p[i]=read();
	for (int i=1;i<=n;++i) a[i]=read(),E[a[i]].push_back(i);
	dfs(s);
	if (a[a[s]]!=s) printf("%lld\n",max(dp[s][1],dp[s][2])+p[s]);
	else
	{
		ans=dp[s][1]-p[s];
		for (int i=0;i<E[s].size();++i)
			if (E[s][i]!=a[s])
				sp.push_back(E[s][i]);
		E[s]=sp,dfs(s),printf("%lld\n",max(dp[s][1],dp[s][2])-p[s]);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 4080kb

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

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: 1ms
memory: 4240kb

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: 1ms
memory: 4332kb

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:

472582069

result:

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