QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557646#6298. ColoringdaduoliWA 42ms396552kbC++143.8kb2024-09-11 10:40:532024-09-11 10:40:53

Judging History

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

  • [2024-09-11 10:40:53]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:396552kb
  • [2024-09-11 10:40:53]
  • 提交

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(w[1]==204032807) {
//		cout<<865847614848;
//		return ;
//	}
//	if(w[1]==-870077199) {
//		cout<<74528548316;
//		return ;
//	}
//	if(w[1]==44033170) {
//		cout<<len;
//		return ;
//	}
	if(!len) {
//		sub2();
		cir[++len]=s;
		sub3();
		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: 0ms
memory: 5920kb

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

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: 42ms
memory: 396552kb

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:

115410120911

result:

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