QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#404092 | #6298. Coloring | ppip | RE | 0ms | 0kb | C++14 | 2.1kb | 2024-05-03 11:33:36 | 2024-05-03 11:33:38 |
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;
}
詳細信息
Test #1:
score: 0
Dangerous Syscalls
input:
3 1 -1 -1 2 1 0 0 3 1 2