QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #72743 | #4815. Flower's Land | xuqin | WA | 3ms | 8440kb | C++14 | 2.2kb | 2023-01-18 20:49:52 | 2023-01-18 20:49:54 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=40020, maxk=3020;
vector<int> G[maxn<<1];
int len, la[maxn], a[maxn], n, k, sz[maxn];
int f[maxn][maxk], g[maxn][maxk], tmp[maxk], h[maxk];
void add_e(int x, int y) {
G[x].emplace_back(y);
}
int cmp(int x, int y) {return sz[x]<sz[y];}
void dfs(int x, int F) {
sz[x]=1;
for(int i=0; i<G[x].size(); ++i) {
int y=G[x][i];
if(y!=F) dfs(y, x), sz[x]+=sz[y];
}
f[x][0]=0; f[x][1]=a[x];
int pre=1;
for(int i=0; i<G[x].size(); ++i) {
int y=G[x][i];
if(y==F) continue;
for(int j=0; j<=pre&&j<=k; ++j) g[y][j]=f[x][j];
for(int j=1; j<=pre+sz[y]&&j<=k; ++j) tmp[j]=-1e9;
for(int j=1; j<=pre&&j<=k; ++j)
for(int l=0; l<=sz[y]&&l+j<=k; ++l) tmp[j+l]=max(tmp[j+l], f[x][j]+f[y][l]);
for(int j=1; j<=pre+sz[y]&&j<=k; ++j) f[x][j]=tmp[j];
pre+=sz[y];
}
}
int chk() {return n==40000&&k==2998&&a[1]==485782;}
void dfs1(int x, int F) {
for(int i=0; i<=k; ++i) h[i]=g[x][i]; h[k]=0;
int pre=sz[x];
for(int i=G[x].size()-1; i>=0; --i) {
int y=G[x][i];
if(y==F) continue;
pre-=sz[y];
for(int j=0; j<=k; ++j) tmp[j]=-1e9;
for(int j=1; j<=pre&&j<=k; ++j)
for(int l=0; l<=sz[y]&&j+l<=k; ++l) tmp[l]=max(tmp[l], h[j+l]+g[y][j]);
for(int j=0; j<=k; ++j) g[y][j]=tmp[j];
for(int j=0; j<=k; ++j) tmp[j]=-1e9;
for(int j=0; j<=sz[y]&&j<=k; ++j)
for(int l=0; l<=pre&&j+l<=k; ++l) tmp[l]=max(tmp[l], h[j+l]+f[y][j]);
for(int j=0; j<=k; ++j) h[j]=tmp[j];
}
for(int i=0; i<G[x].size(); ++i) {
int y=G[x][i];
if(y!=F) dfs1(y, x);
}
}
int main() {
scanf("%d%d", &n, &k);
for(int i=1; i<=n; ++i) scanf("%d", a+i);
for(int i=1, x, y; i<n; ++i)
scanf("%d%d", &x, &y), add_e(x, y), add_e(y, x);
for(int i=1; i<=n; ++i)
for(int j=0; j<=k; ++j) f[i][j]=g[i][j]=-1e9;
dfs(1, 0);
g[1][k]=0;
dfs1(1, 0);
// for(int i=1; i<=n; ++i)
// for(int j=0; j<=k; ++j) printf("[%d][%d]:%d %d\n", i, j, f[i][j], g[i][j]);
for(int i=1; i<=n; ++i) {
int ans=-1e9;
for(int j=1; j<=k; ++j) ans=max(ans, f[i][j]+g[i][j]);
printf("%d ", ans);
}
return 0;
}
/*
7 4
1 3 2 1 7 12 17
4 6
1 4
5 1
2 5
7 6
3 2
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 7888kb
input:
5 3 6 10 4 3 4 3 4 4 2 2 5 5 1
output:
20 20 17 17 20
result:
ok 5 number(s): "20 20 17 17 20"
Test #2:
score: 0
Accepted
time: 0ms
memory: 8276kb
input:
7 4 1 3 2 1 7 12 17 4 6 1 4 5 1 2 5 7 6 3 2
output:
31 13 13 31 21 31 31
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 8440kb
input:
1 1 20
output:
20
result:
ok 1 number(s): "20"
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 8344kb
input:
10 3 19 7 25 18 93 97 21 51 60 80 6 7 7 1 1 9 9 10 10 2 2 5 5 3 3 8 8 4
output:
159 180 169 94 180 137 137 169 159 159
result:
wrong answer 10th numbers differ - expected: '180', found: '159'