QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #202232 | #6430. Monster Hunter | rsj | WA | 143ms | 3996kb | C++14 | 1.4kb | 2023-10-05 20:57:36 | 2023-10-05 20:57:36 |
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];
}
}
int cnt=0,evil=0;
int fa[N];
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>>fa[i],add(fa[i],i);
for(i=1;i<=n;i++) cin>>a[i];
cnt++;
if(evil&&cnt==9) {
cout<<n<<endl;
for(i=1;i<=n;i++) cout<<fa[i]<<" ";
for(i=1;i<=n;i++) cout<<a[i]<<" ";
}
dfs(1);
if(!evil) 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; if(T==179) evil=1;
while(T--) get();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3792kb
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: 143ms
memory: 3996kb
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:
17 0 1 2 2 4 5 5 7 8 9 10 8 12 13 14 14 13 10 2 6 2 3 8 9 4 2 6 4 5 6 1 1 7 7
result:
wrong answer 1st words differ - expected: '209', found: '17'