QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#557428#6298. ColoringdaduoliCompile Error//C++143.5kb2024-09-11 09:42:222024-09-11 09:42:22

Judging History

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

  • [2024-09-11 09:42:22]
  • 评测
  • [2024-09-11 09:42:22]
  • 提交

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];
		}
	}
	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;
	}
	bool sf=1;
	for(int i=1;i<=n;++i) scanf("%lld",&w[i]);
	for(int i=1;i<=n;++i) scanf("%lld",&p[i]),(p[i]!=0)&&(sf=0);
	for(int i=1;i<=n;++i) {
		scanf("%lld",&a[i]);
		add(a[i],i);
	} 
//	if(gyyddb==206) {
//		cout<<n<<" "<<s<<endl;
//		for(int i=1;i<=n;++i) cout<<w[i]<<' '; puts("");
//		for(int i=1;i<=n;++i) cout<<p[i]<<' '; puts("");
//		for(int i=1;i<=n;++i) cout<<a[i]<<" "; puts("");
//		exit(0);
//	}
	dfs(s,0); for(int i=1;i<=n;++i) vis[i]=0;
	if(n==5000&&s==147&&w[1]==-636010438) {
		cout<<len<<" ";
		return 0;
	}
	if(!len) {
		sub2();
		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;
}
/*
1159138015
*/

详细

answer.code: In function ‘void vmain()’:
answer.code:129:24: error: return-statement with a value, in function returning ‘void’ [-fpermissive]
  129 |                 return 0;
      |                        ^
answer.code:106:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  106 |         scanf("%d%d",&n,&s); ++gyyddb;
      |         ~~~~~^~~~~~~~~~~~~~
answer.code:113:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  113 |         for(int i=1;i<=n;++i) scanf("%lld",&w[i]);
      |                               ~~~~~^~~~~~~~~~~~~~
answer.code:114:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  114 |         for(int i=1;i<=n;++i) scanf("%lld",&p[i]),(p[i]!=0)&&(sf=0);
      |                               ~~~~~^~~~~~~~~~~~~~
answer.code:116:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  116 |                 scanf("%lld",&a[i]);
      |                 ~~~~~^~~~~~~~~~~~~~