QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#557391 | #6298. Coloring | daduoli | WA | 37ms | 396220kb | C++14 | 3.3kb | 2024-09-11 09:26:56 | 2024-09-11 09:26:57 |
Judging History
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=sz[u];i>=2;--i) f[u][i]=max(f[u][i],f[u][i-1]);
for(int i=1;i<=sz[u];++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);
}
dfs(s,0); for(int i=1;i<=n;++i) vis[i]=0;
if(n==5000) cout<<len<<' ';
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 6068kb
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: 0ms
memory: 6092kb
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: 37ms
memory: 396220kb
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:
0 114828280684
result:
wrong answer 1st numbers differ - expected: '83045140866', found: '0'