QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#404094 | #6298. Coloring | ppip | WA | 56ms | 199816kb | C++14 | 2.1kb | 2024-05-03 11:34:05 | 2024-05-03 11:34:27 |
Judging History
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'