QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #202207 | #6430. Monster Hunter | rsj | WA | 144ms | 3752kb | C++14 | 1.1kb | 2023-10-05 20:44:07 | 2023-10-05 20:44:08 |
Judging History
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=2;i<=n;i++) cin>>x,add(x,i);
for(i=1;i<=n;i++) cin>>a[i];
for(i=0;i<=n;i++) for(j=0;j<=n;j++) f[i][j][0]=f[i][j][1]=1e16; 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() {
int T; cin>>T;
while(T--) get();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
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:
29 16 9 4 1 0 74 47 35 25 15 11 7 3 1 0 145 115 93 73 55 42 32 22 14 8 4 1 0
result:
ok 29 tokens
Test #2:
score: -100
Wrong Answer
time: 144ms
memory: 3752kb
input:
179 20 1 1 1 4 5 5 7 7 9 9 11 12 13 14 5 16 17 16 19 3 9 3 2 7 7 2 8 5 7 5 4 7 4 2 4 9 2 7 9 19 1 1 3 4 3 6 7 6 6 10 10 12 13 13 12 16 16 18 8 8 3 6 10 1 1 1 2 2 3 3 3 10 5 5 7 10 5 2 1 10 4 2 1 2 7 14 1 1 3 4 4 6 4 8 9 10 11 8 13 4 4 6 6 10 8 9 5 7 1 4 7 9 8 6 1 2 3 3 5 2 7 5 6 1 6 11 1 2 3 3 5 6 6...
output:
209 182 159 137 117 99 81 65 56 47 39 32 25 19 15 11 8 6 4 2 0 178 151 129 108 89 74 64 54 44 36 29 23 18 13 10 7 5 2 1 0 18 4 0 16 2 0 172 137 111 93 78 63 49 39 31 23 16 10 5 1 0 52 33 21 9 3 1 0 109 72 53 39 29 22 16 10 5 2 1 0 105 69 47 35 25 17 12 7 3 0 -52 -52 -52 -52 -52 -52 -52 -52 -52 -52 -...
result:
wrong answer 92nd words differ - expected: '156', found: '-52'