QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#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

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-01-18 20:49:54]
评测

测评结果：WA
用时：3ms
内存：8440kb

查看

[2023-01-18 20:49:52]
提交

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
*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 3ms

memory: 7888kb

input:

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:

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'