QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404092#6298. ColoringppipRE 0ms0kbC++142.1kb2024-05-03 11:33:362024-05-03 11:33:38

Judging History

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

  • [2024-05-03 11:33:38]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-05-03 11:33:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
constexpr int Spp{1<<20};
char buf[Spp],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,Spp,stdin),p1==p2)?EOF:*p1++)
template <typename T>
void read(T &x) {
	char c;int f{1};
	do x=(c=getchar())^48;
	while (!isdigit(c)&&c!='-');
	if (x==29) f=-1,x=0;
	while (isdigit(c=getchar()))
		x=(x<<3)+(x<<1)+(c^48);
	x*=f;
}
template <typename T,typename ...Args>
void read(T& x,Args&... args) {read(x);read(args...);}
constexpr int N{5005};
#define int long long
int w[N+5],p[N+5],fa[N+5];
bool rin[N+5];
vector<int> e[N+5];
int f[N+5][N+5];
int n,s;
void solve(int u) {
	for (auto v:e[u]) {
		solve(v);
		for (int i{0};i<=n+5;++i) f[u][i]+=f[v][i];
	}
	f[u][1]=max(0LL,f[u][0]+w[u]-p[u]);
	for (int i{2};i<=n+5;++i)
		f[u][i]=max(f[u][i-1],(i&1)*w[u]-p[u]*i+f[u][i]);
}
int g[2][N+5][N+5],nxt[N+5];
int sum[N+5][N+5];
signed main() {
	freopen("cheese.in","r",stdin);
	freopen("cheese.out","w",stdout);
	read(n,s);
	for (int i{1};i<=n;++i) read(w[i]);
	for (int i{1};i<=n;++i) read(p[i]);
	for (int i{1};i<=n;++i) read(fa[i]),e[fa[i]].push_back(i);
	int x{s},y{fa[s]};
	while (x!=y) x=fa[x],y=fa[fa[y]];
	do {
		rin[y]=true;
		e[fa[y]].erase(find(e[fa[y]].begin(),e[fa[y]].end(),y));
		solve(fa[y]);
		y=fa[y];
	} while (y!=x);
	if (!rin[s]) {
		int ans[2]{0,0};
		for (auto v:e[s])
			for (auto k:{0,1})
				ans[k]+=f[v][k];
		cout<<max(ans[0]+w[s],ans[1]-p[s])<<endl;
		// cout<<f[s][1]<<endl;
		return 0;
	}
	x=y=s;
	int m{0},pp{0};
	do {
		nxt[fa[y]]=y;
		y=fa[y];
	} while (y!=x);
	x=y=s;
	do {
		++m;
		pp+=p[y];
		for (auto v:e[y])
			for (int i{0};i<=n+5;++i) sum[i][m]+=f[v][i];
		y=nxt[y];
	} while (y!=x);
	for (int k{0};k<=n+5;++k) partial_sum(sum[k]+1,sum[k]+m+1,sum[k]+1);
	int ans{0};
	// for (int i{1};i<=n;++i) cerr<<i<<" "<<w[i]-p[i]<<endl;
	for (int i{0};i<=n;++i) {
		int prv{0},P{0},W{0},C{s};
		for (int j{1};j<=m;++j) {
			P+=p[C];
			W+=w[C];
			C=nxt[C];
			prv=max(prv,sum[i+2][j]-sum[i+1][j]-P-W);
			ans=max(ans,-2*pp*i+sum[i][m]+(sum[i+1][j]-sum[i][j]+W-P+p[s])+prv);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

3 1
-1 -1 2
1 0 0
3 1 2

output:


result: