QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404094#6298. ColoringppipWA 56ms199816kbC++142.1kb2024-05-03 11:34:052024-05-03 11:34:27

Judging History

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

  • [2024-05-03 11:34:27]
  • 评测
  • 测评结果:WA
  • 用时:56ms
  • 内存:199816kb
  • [2024-05-03 11:34:05]
  • 提交

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() {
	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: 100
Accepted
time: 1ms
memory: 3604kb

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

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: 56ms
memory: 199816kb

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:

804501804

result:

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