QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300785#6298. Coloringkid_magicWA 83ms395704kbC++142.8kb2024-01-08 20:03:232024-01-08 20:03:23

Judging History

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

  • [2024-01-08 20:03:23]
  • 评测
  • 测评结果:WA
  • 用时:83ms
  • 内存:395704kb
  • [2024-01-08 20:03:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
int n,s;
int a[MAXN];
int w[MAXN];
int p[MAXN];
vector<int>g[MAXN];
int Rd[MAXN];
int vis[MAXN];
int Lorp[MAXN];
int cnt_lorp;
void Find_lorp(int x)
{
	if(vis[x])
	{
		return;
	}
	vis[x]=1;
	Lorp[++cnt_lorp]=x;
	Find_lorp(a[x]);
}
bool fxw=0;
int oex[MAXN];
long long dp[MAXN][MAXN],Pre[MAXN][MAXN];
void dfs(int x,int f)
{
	for(int i=0;i<g[x].size();i++)
	{
		int v=g[x][i];
		if(v==f)
		{
			continue;
		}
		if(Rd[v])
		{
			continue;
		}
		dfs(v,x);
	}
	
	for(int i=0;i<=n+1;i++)
	{
		dp[x][i]=(long long)w[x]*((i&1))-((long long)i*p[x]);
		for(int j=0;j<g[x].size();j++)
		{
			int v=g[x][j];
			if(v==f)
			{
				continue;
			}
			if(Rd[v])
			{
				continue;
			}
			dp[x][i]+=Pre[v][i];
		}
	}
	if(x==s)
	{
		dp[x][0]=-2e18;
	}
	Pre[x][0]=dp[x][0];
	for(int i=1;i<=n+1;i++)
	{
		Pre[x][i]=max(Pre[x][i-1],dp[x][i]);
	}
	if(s==x)
	{
		fxw=1;
	}

}
int Nox[MAXN];
long long F[MAXN][3];
int main()
{
	// freopen("date.in","r",stdin);
	// freopen("date.out","w",stdout);
	scanf("%d %d",&n,&s);
	oex[s]=1;
	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]);
		g[a[i]].push_back(i);
		Rd[a[i]]++;
	}
	queue<int>Q;
	for(int i=1;i<=n;i++)
	{
		if(!Rd[i])
		{
			Q.push(i);
		}
	}
	while(Q.size())
	{
		int tmp=Q.front();
		Q.pop();
		Rd[a[tmp]]--;
		if(!Rd[a[tmp]])
		{
			Q.push(a[tmp]);
		}
	}

	for(int i=1;i<=n;i++)
	{
		if(Rd[i]&&(!vis[i]))
		{
			//cerr<<i<<endl;
			cnt_lorp=0;
			Find_lorp(i);
			for(int j=1;j<=cnt_lorp;j++)
			{
				//cerr<<Lorp[j]<<endl;
				dfs(Lorp[j],0);
			}
			if(fxw)
			{
				if(vis[s])
				{
					reverse(Lorp+1,Lorp+1+cnt_lorp);
					int Sta;
					for(int j=1;j<=cnt_lorp;j++)
					{
						if(Lorp[j]==s)
						{
							Sta=j;
						}
					}
					
					for(int j=1;j<=cnt_lorp;j++)
					{
						Nox[j]=Lorp[(Sta+j-2)%cnt_lorp+1];
					}
					for(int j=1;j<=cnt_lorp;j++)
					{
						Lorp[j]=Nox[j];
						//printf("%d ",Lorp[j]);
					}
					long long Res=-2e18;

					for(int x=0;x<=n;x++)
					{
						F[1][0]=dp[Lorp[1]][x+1];
						F[1][1]=F[1][2]=-2e18;
						for(int j=2;j<=cnt_lorp;j++)
						{
							F[j][0]=F[j][1]=F[j][2]=-2e18;
							F[j][0]=F[j-1][0]+dp[Lorp[j]][x+1];
							F[j][1]=max(F[j-1][0],F[j-1][1])+dp[Lorp[j]][x];
							if(x)
							{
								F[j][2]=max(F[j-1][0],max(F[j-1][2],F[j-1][1]))+dp[Lorp[j]][x-1];
							}
							
						}
						Res=max(Res,max(F[cnt_lorp][0],max(F[cnt_lorp][1],F[cnt_lorp][2])));
					}
					printf("%lld\n",Res+p[s]);
				}
				else
				{
					printf("%lld\n",max(dp[s][2],dp[s][1])+p[s]);
				}
				return 0;
			}

		}
	}

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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: 83ms
memory: 395704kb

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: 79ms
memory: 395424kb

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'