QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#770507 | #7966. 采矿 | little_pinkpig | WA | 154ms | 81740kb | C++14 | 4.8kb | 2024-11-21 22:08:02 | 2024-11-21 22:08:04 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define MAXN (305)
#define MAXQ (605)
using namespace std;
const ll inf=1e16;
template<typename type>
void read(type &x)
{
bool f=0;char ch=0;x=0;
while(ch<'0'||ch>'9'){f|=!(ch^'-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x=f?-x:x;
}
template<typename type,typename... Args>
void read(type &x,Args &... args)
{
read(x);
read(args...);
}
int n,q,s,tot,pcnt;
int fa[MAXN],r[MAXN],p[MAXN],siz[MAXN],ind[MAXN],dfn[MAXN];
ll ans=-inf;
ll f[MAXN][MAXN][MAXN],g[MAXN][MAXN][MAXN],h[MAXN][MAXN];
vector<int> G[MAXN];
vector<ll> vec[2][MAXN];
inline bool chk(int u,int v){return dfn[v]>=dfn[u]&&dfn[v]<=dfn[u]+siz[u]-1;}
void dfs(int u)
{
siz[ind[dfn[u]=++tot]=u]=1;
for(int v:G[u]) if(v) dfs(v),siz[u]+=siz[v];
}
inline void mset()
{
for(int i=1;i<=n;i++) for(int j=0;j<=siz[G[i][0]];j++) for(int k=0;k<=siz[G[i][1]];k++) f[i][j][k]=-inf;
for(int i=1;i<=n;i++) for(int j=0;j<=n;j++) h[i][j]=-inf;
}
inline void cset(){for(int i=1;i<=n;i++) for(int j=0;j<=siz[G[i][0]];j++) for(int k=0;k<=siz[G[i][1]];k++) g[i][j][k]=f[i][j][k];}
inline ll calc(int u,int o,int v){if(!u) return 0;return vec[o][u][v];}
void work(int o)
{
if(o==1)
{
for(int i=2;i<=n;i++)
for(int j=0;j<=siz[G[i][0]];j++)
for(int k=0;k<=siz[G[i][1]];k++)
if(pcnt-j-k<n-siz[i])
h[i][j+k]=max(h[i][j+k],g[i][j][k]);
for(int x=n,i;x;x--)
{
i=ind[x];
for(int j=0;j<=siz[G[i][0]];j++)
{
for(int k=0;k<=siz[G[i][1]];k++)
{
if(j+k<=pcnt&&pcnt-j-k<=n-siz[i])
{
if(G[i][0]) f[i][j][k]=max(f[i][j][k],h[G[i][0]][j]);
if(G[i][1]) f[i][j][k]=max(f[i][j][k],h[G[i][1]][k]);
if(pcnt-j-k<n-siz[i]) h[i][j+k]=max(h[i][j+k],f[i][j][k]);
}
}
}
}
}
if(o==2)
{
for(int i=1;i<=n;++i)
{
for(int j=0;j<=siz[G[i][0]];j++)
{
for(int k=0;k<=siz[G[i][1]];k++)
{
if(G[i][0]&&j<siz[G[i][0]]) h[G[i][0]][j]=max(h[G[i][0]][j],g[i][j][k]);
if(G[i][1]&&k<siz[G[i][1]]) h[G[i][1]][k]=max(h[G[i][1]][k],g[i][j][k]);
}
}
}
for(int x=n,i;x;x--)
{
i=ind[x];
for(int j=0;j<=siz[G[i][0]];j++)
{
for(int k=0;k<=siz[G[i][1]];k++)
{
f[i][j][k]=max(f[i][j][k],h[i][j+k]);
if(G[i][0]&&j<siz[G[i][0]]) h[G[i][0]][j]=max(h[G[i][0]][j],f[i][j][k]);
if(G[i][1]&&k<siz[G[i][1]]) h[G[i][1]][k]=max(h[G[i][1]][k],f[i][j][k]);
}
}
}
}
if(o==3)
{
for(int i=1;i<=n;i++)
for(int j=0;j<=siz[G[i][0]];j++)
for(int k=0;k<=siz[G[i][1]];k++)
if(pcnt-j-k<n-siz[i])
f[i][j][k]=g[i][j][k];
++pcnt;
}
if(o==4)
{
for(int i=1;i<=n;i++)
for(int j=0;j<=siz[G[i][0]];j++)
for(int k=0;k<=siz[G[i][1]];k++)
if(pcnt-j-k>0)
f[i][j][k]=g[i][j][k];
--pcnt;
}
for(int i=1;i<=n;i++)
for(int j=0;j<=siz[G[i][0]];j++)
for(int k=0;k<=siz[G[i][1]];k++)
if(f[i][j][k]>=0)
f[i][j][k]+=calc(G[i][0],0,j)+calc(G[i][1],0,k)+calc(i,1,pcnt-j-k)+r[i];
return;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
read(n,q,s);
for(int i=2;i<=n;i++) read(fa[i]),G[fa[i]].push_back(i);
for(int i=2;i<=n;i++) read(r[i]);
for(int i=2;i<=n;i++) read(p[i]);
for(int i=1;i<=n;i++) while(G[i].size()<2) G[i].push_back(0);
dfs(1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(chk(i,j)) vec[0][i].push_back(p[j]);
else vec[1][i].push_back(p[j]);
}
for(int o=0;o<2;o++)
{
sort(vec[o][i].begin(),vec[o][i].end(),greater<int>());
vec[o][i].insert(vec[o][i].begin(),0);
for(int j=1;j<(int)vec[o][i].size();j++) vec[o][i][j]+=vec[o][i][j-1];
}
}
mset();
f[s][0][0]=0;
for(int i=1,o;i<=q;++i)
{
read(o);
cset(),mset(),work(o);
}
for(int i=1;i<=n;i++) for(int j=0;j<=siz[G[i][0]];j++) for(int k=0;k<=siz[G[i][1]];k++) ans=max(ans,f[i][j][k]);
if(ans<0) printf("No solution.");
else printf("%lld",ans);
}
详细
Test #1:
score: 0
Wrong Answer
time: 154ms
memory: 81740kb
input:
300 600 175 1 2 1 4 4 2 7 8 9 8 3 5 12 10 6 6 13 15 9 11 11 13 15 22 14 26 27 12 5 16 10 24 23 16 33 34 21 22 37 39 17 39 40 20 36 28 40 33 48 29 26 46 46 18 37 32 20 38 54 45 19 30 52 27 18 60 41 57 30 50 48 47 65 17 35 14 55 24 78 80 71 81 28 3 21 19 63 35 75 75 73 92 89 36 81 50 34 93 85 43 42 78...
output:
No solution.
result:
wrong answer 1st lines differ - expected: '4588927051034', found: 'No solution.'