QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #202219 | #6430. Monster Hunter | rsj | TL | 0ms | 0kb | C++14 | 1.2kb | 2023-10-05 20:50:52 | 2023-10-05 20:50:54 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2077;
#define int long long
struct edge {
int to;
edge *nex;
}*head[N];
void add(int u,int v) {
edge *cur=new edge;
cur->to=v;
cur->nex=head[u];
head[u]=cur;
}
int f[N][N][2],siz[N],a[N],n; //1 Existed 0 Destructed
void chmin(int &x,int y) {
x=min(x,y);
}
void dfs(int u) {
siz[u]=1;
for(edge *cur=head[u];cur;cur=cur->nex) {
dfs(cur->to);
siz[u]+=siz[cur->to];
}
f[u][1][1]=2*a[u];
f[u][0][0]=0;
int i,j;
for(edge *cur=head[u];cur;cur=cur->nex) {
for(i=siz[u];i>=0;i--) {
for(j=siz[cur->to];j>0;j--) {
chmin(f[u][i+j][1],f[u][i][1]+min(f[cur->to][j][1],f[cur->to][j][0]));
chmin(f[u][i+j][0],f[u][i][0]+min(f[cur->to][j][1]-a[cur->to],f[cur->to][j][0]));
}
}
siz[u]+=siz[cur->to];
}
}
void get() {
int i,j,x;
cin>>n;
for(i=1;i<=n;i++) head[i]=0;
for(i=0;i<=n;i++) for(j=0;j<=n;j++) f[i][j][0]=f[i][j][1]=1e16;
for(i=2;i<=n;i++) cin>>x,add(x,i);
for(i=1;i<=n;i++) cin>>a[i];
dfs(1);
for(i=n;i>=0;i--) cout<<min(f[1][i][1]-a[1],f[1][i][0])<<" \n"[i==0];
}
signed main() {
freopen("1.in","r",stdin);
int T; cin>>T;
while(T--) get();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 5 1 2 3 4 1 2 3 4 5 9 1 2 3 4 3 4 6 6 8 4 9 4 4 5 2 4 1 12 1 2 2 4 5 3 4 3 8 10 11 9 1 3 5 10 10 7 3 7 9 4 9
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...