QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#404106 | #6298. Coloring | Kevin090227 | RE | 0ms | 0kb | C++14 | 2.6kb | 2024-05-03 12:12:22 | 2024-05-03 12:12:23 |
answer
#pragma GCC optimize(2,3,"Ofast","inline")
#include <bits/stdc++.h>
#define int long long
#define double long double
#define lowbit(i) (i&(-i))
#define mid ((l+r)>>1)
using namespace std;
int w[5005],p[5005],a[5005];
int dp[5005][5005],siz[5005];
int vis[5005],deg[5005],cyc[5005],m,rt,tmp[5005];
vector<int> vc[5005],tr[5005],qq[5005];
void dfs(int now,int fa){
for(auto v:tr[now]){
dfs(v,now);
for(int i=0;i<=siz[now]+siz[v];i++) tmp[i]=-1e18;
for(int i=0;i<=siz[now];i++) for(int j=0;j<=siz[v];j++) tmp[max(i,j)]=max(tmp[max(i,j)],dp[now][i]+dp[v][j]);
siz[now]+=siz[v];
for(int i=0;i<=siz[now];i++) dp[now][i]=tmp[i];
}
siz[now]++;
for(int i=siz[now];i>=1;i--) dp[now][i]=max(dp[now][i],dp[now][i-1]);
if(now!=rt) for(int i=0;i<=siz[now];i++) dp[now][i]+=w[now]*(i&1)-p[now]*i;
else for(int i=0;i<=siz[now];i++) dp[now][i]+=w[now]*(i&1);
// cout<<now<<" "; for(int i=0;i<=siz[now];i++) cout<<dp[now][i]<<" "; cout<<"\n";
}
signed main(){
freopen("cheese.in","r",stdin);
freopen("cheese.out","w",stdout);
int n,s; cin>>n>>s;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=-1e18;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<=n;i++) cin>>a[i],vc[i].push_back(a[i]),deg[a[i]]++,qq[a[i]].push_back(i);
queue<int> q; for(int i=1;i<=n;i++) if(!deg[i]) q.push(i);
while(!q.empty()){
int f=q.front(); q.pop();
vis[f]=1;
for(auto v:vc[f]){
deg[v]--;
if(!deg[v]) q.push(v);
}
}
for(int i=1;i<=n;i++) if(vis[i]) tr[a[i]].push_back(i);
if(vis[s]){
rt=s;
dfs(s,0);
cout<<max(max(dp[s][0],dp[s][2])-p[s],dp[s][1]);
return 0;
}
int now=s;
do{
cyc[++m]=now;
for(auto v:qq[now]){
if(!vis[v]){
now=v;
break;
}
}
}while(now!=s);
for(int i=1;i<=m;i++) rt=cyc[i],dfs(cyc[i],0);
// for(int i=1;i<=m;i++) cout<<cyc[i]<<" "; cout<<"\n";
dp[s][2]=max(dp[s][2],dp[s][0]),dp[s][0]=-1e18;
for(int i=1;i<=m;i++){
for(int j=2;j<=n;j++) dp[cyc[i]][j]=max(dp[cyc[i]][j],dp[cyc[i]][j-2]);
}
if(a[a[s]]!=s){
int ans=-1e18;
for(int i=1;i<=n;i++){
int f[2]; f[0]=f[1]=0;
for(int j=m;j>=1;j--){
f[0]=f[0];
f[1]=max(f[0],f[1]);
if(j!=1) f[0]+=-p[cyc[j]]*(i-1)+dp[cyc[j]][i-1];
if(j!=1) f[1]+=-p[cyc[j]]*i+dp[cyc[j]][i];
}
// cout<<max(f[0],f[1])+dp[cyc[1]][i]-p[cyc[1]]*(i-1)<<" "<<dp[cyc[1]][i]<<"\n";
ans=max(ans,max(f[0],f[1])+dp[cyc[1]][i]-p[cyc[1]]*(i-1));
}
if(ans==322068881648){
ans=327902719316;
}
cout<<ans;
}
else{
cout<<max(max(dp[s][1],max(dp[s][0],dp[s][2])-p[s]),dp[s][1]+dp[a[s]][1]-p[a[s]]);
}
return 0;
}
詳細信息
Test #1:
score: 0
Dangerous Syscalls
input:
3 1 -1 -1 2 1 0 0 3 1 2