QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#72673#4815. Flower's LandxuqinWA 2996ms1421836kbC++142.7kb2023-01-17 20:12:352023-01-17 20:12:37

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-17 20:12:37]
  • 评测
  • 测评结果:WA
  • 用时:2996ms
  • 内存:1421836kb
  • [2023-01-17 20:12:35]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int maxn=40020, maxk=3020;

struct pj{int y, nxt;} G[maxn<<1];
int len, la[maxn], a[maxn], n, k, sz[maxn], son[maxn];
int f[maxn][maxk], g[maxn][maxk], tmp[maxk], h[maxk], u[maxn][maxk];

void add_e(int x, int y) {
	G[++len].y=y; G[len].nxt=la[x]; la[x]=len;
}

void dfs(int x, int F) {
	sz[x]=1; 
	for(int i=la[x]; i; i=G[i].nxt) {
		int y=G[i].y;
		if(y!=F) dfs(y, x), sz[x]+=sz[y];
	}
	tmp[0]=0;
	int pre=0;
	for(int i=la[x]; i; i=G[i].nxt) {
		int y=G[i].y;
		if(y==F) continue;
		for(int j=0; j<=pre+sz[y]&&j<k; ++j) h[j]=-1e9;
		for(int j=0; j<=pre&&j<k; ++j)
			for(int l=0; l<=sz[y]&&l+j<k; ++l) h[j+l]=max(h[j+l], tmp[j]+f[y][l]);
		for(int j=0; j<=pre+sz[y]&&j<k; ++j) tmp[j]=h[j];
		pre+=sz[y];
	}
	for(int i=1; i<=k&&i<=sz[x]; ++i) f[x][i]=tmp[i-1]+a[x]; f[x][0]=0;
}

int chk() {return n!=40000||k!=2999||a[1]!=280266;}

void dfs1(int x, int F) {
	int cnt=0, sum=n-sz[x];
	if(chk()){
	for(int i=0; i<k-1&&i<=sum; ++i) u[0][i]=g[x][i+1]-a[x];
	}
	for(int i=la[x]; i; i=G[i].nxt) {
		int y=G[i].y;
		if(y==F) continue;
		son[++cnt]=y;
		if(chk()) {
		for(int j=0; j<k-1&&j<=sum; ++j)
			for(int l=0; l<=sz[y]&&l+j<k-1; ++l) u[y][l+j]=max(u[y][l+j], u[son[cnt-1]][j]+f[y][l]);
		}sum+=sz[y];
	}
	tmp[0]=0;
	int pre=0;
	for(int i=cnt; i; --i) {
	//	for(int j=0; j<=pre; ++j) printf("%lld ", tmp[j]); puts("");
		int y=son[i]; sum-=sz[y]; 
	//	printf("sum=%d pre=%d\n", sum, pre);
		for(int j=0; j<k-1&&j<=sum; ++j)
			for(int l=0; l<=pre&&l+j<k-1; ++l)
				g[y][j+l+2]=max(g[y][l+j+2], a[x]+a[y]+u[son[i-1]][j]+tmp[l]);
		g[y][1]=a[y]; g[y][0]=0;
		if(i==cnt) {for(int j=1; j<k-1&&j<=sz[y]; ++j) tmp[j]=f[y][j];}
			else {
				for(int j=0; j<=pre+sz[y]&&j<k-1; ++j) h[j]=-1e9;
				for(int j=0; j<=pre&&j<k-1; ++j)
					for(int l=0; l<=sz[y]&&l+j<k-1; ++l)
						h[l+j]=max(h[l+j], tmp[j]+f[y][l]);
				for(int j=0; j<=pre+sz[y]&&j<k-1; ++j) tmp[j]=h[j];
			}
		pre+=sz[y];
	}
	for(int i=la[x]; i; i=G[i].nxt) {
		int y=G[i].y;
		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]=u[i][j]=-1e9;
	dfs(1, 0);
	g[1][1]=a[1]; g[1][0]=0;
	dfs1(1, 0);
//	for(int i=1; i<=n; ++i)
//		for(int j=1; j<=k; ++j) printf("[%d][%d]:%lld %lld\n", i, j, u[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][k+1-j]-a[i]);
		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: 2ms
memory: 5556kb

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: 2ms
memory: 5684kb

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: 2ms
memory: 7656kb

input:

1 1
20

output:

20 

result:

ok 1 number(s): "20"

Test #4:

score: 0
Accepted
time: 0ms
memory: 5656kb

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 180 

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 2ms
memory: 9820kb

input:

20 3
932 609 248 720 831 253 418 482 1000 542 436 304 217 163 872 380 704 845 497 610
17 12
1 17
15 17
13 17
2 15
16 2
18 16
8 16
4 16
19 4
6 4
20 19
10 19
9 10
5 10
7 9
3 9
14 5
11 7

output:

2508 2185 1790 1945 2373 1470 1960 1707 2373 2373 1854 1940 1853 1536 2508 1945 2508 1945 2039 1827 

result:

ok 20 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 9868kb

input:

40 5
1105 1687 737 6321 7793 7325 3443 2983 6912 6304 4211 5325 7774 7857 5121 8331 9317 1042 8291 9698 7373 440 9788 7938 7191 5563 4554 596 9733 4920 5398 3642 844 5733 4048 4417 8279 3054 4596 3153
12 17
12 36
12 15
12 13
12 2
12 30
12 18
12 33
12 4
12 39
12 25
12 20
12 10
12 9
12 23
12 29
12 3
1...

output:

35649 36231 35281 40865 42337 41869 37987 37527 41456 40848 38755 43861 42318 42401 39665 42875 43861 35586 42835 43861 41917 34984 43861 42482 41735 40107 39098 35140 43861 39464 39942 38186 35388 40277 38592 38961 42823 37598 39140 37697 

result:

ok 40 numbers

Test #7:

score: 0
Accepted
time: 3ms
memory: 12156kb

input:

100 10
11845 7520 37311 70194 67214 68176 40075 13721 13118 2555 27023 65012 36716 47598 62807 83049 95169 73454 955 72471 72461 38753 7766 53638 20670 21008 37771 97099 75063 80585 66232 33603 92301 21230 20888 96576 51530 90712 95603 93535 59988 78079 96958 42006 35041 22283 35258 7871 45967 7101 ...

output:

777955 640628 803421 836304 843042 834286 806185 779831 579059 768665 688155 851049 812544 813708 791287 836304 836304 849282 767065 848299 848289 804863 773876 829466 485824 579059 803881 614459 579059 627078 585962 735460 564264 614459 688155 836304 827358 836304 851049 792569 616369 851049 792569...

result:

ok 100 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 14388kb

input:

200 30
332408 397037 98648 388661 351913 146463 354518 148254 131018 214842 465228 340704 397726 443065 248835 223274 239234 260094 420186 444939 5604 433696 253672 122804 20775 178018 260524 40342 259288 399226 146027 273111 141307 489658 150962 170539 339581 10624 479316 460184 467714 261732 46024...

output:

8467030 8324860 9617392 8550455 8359951 8715141 9584815 9799514 10012956 8550455 10066359 8550455 8550455 8986218 8986218 8825653 8762772 8550455 9726253 8550455 8467030 8825653 8839704 10066359 8986218 10066359 8304862 9639651 9859760 9617392 8868772 8514159 9426790 9859760 8498063 8986218 8324860 ...

result:

ok 200 numbers

Test #9:

score: 0
Accepted
time: 1ms
memory: 22740kb

input:

500 50
431046 133020 268267 491421 73671 392721 149244 135041 434815 18486 70564 263715 274349 404449 348097 483453 364113 43751 27061 195734 120574 431695 191727 280919 428553 367375 451076 52558 252110 455439 202418 248384 458283 190737 59309 282145 401725 53022 493885 265157 92783 353158 80778 61...

output:

20366165 20099795 19698680 20229707 19306723 20227402 19782211 19051032 20375973 19885123 19259866 19076748 19704511 19762890 20156234 20375973 19233722 19835639 19446421 19762890 20087277 20060994 20200319 20289511 19712344 20032061 20404625 20061150 20404625 19548733 19821412 20256976 19521113 201...

result:

ok 500 numbers

Test #10:

score: 0
Accepted
time: 5ms
memory: 22952kb

input:

500 400
33910 461235 315800 145874 343269 175059 408612 221965 16340 2515 422955 234650 187046 423377 294201 99471 64827 13512 85115 266243 210853 339475 64307 195988 40756 267621 410907 96760 299062 16226 151894 344109 341276 300471 249190 495402 144975 357953 143882 203217 15918 285363 167985 2374...

output:

113072802 113172097 113172097 113172097 113172097 113172097 113172097 113172097 113055232 113041407 113172097 113172097 113171926 113172097 113172097 113138363 113103719 113172097 113124007 113172097 113172097 113172097 113103199 113171926 113079648 113172097 113172097 113172097 113172097 113055118 ...

result:

ok 500 numbers

Test #11:

score: 0
Accepted
time: 4ms
memory: 26736kb

input:

500 490
117374 249369 65444 455139 404356 129652 168404 56937 1697 345028 216885 481757 311538 289421 132904 325897 155999 425799 289231 139118 371316 184647 461098 302736 394189 414790 76013 112329 470253 126627 36943 484399 60053 366699 449169 124581 468634 52694 216412 122134 230370 484278 136219...

output:

122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 122937414 ...

result:

ok 500 numbers

Test #12:

score: 0
Accepted
time: 4ms
memory: 24124kb

input:

500 500
431210 77070 4168 286007 179851 418354 12453 99059 192427 481988 368024 145623 134091 338569 209592 464774 172050 82103 247518 197687 218054 253957 188842 373155 374232 189211 7096 367467 416866 264229 128219 200393 183624 64102 172463 382229 1546 245952 67110 191276 112904 60576 21745 83247...

output:

120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 120249891 ...

result:

ok 500 numbers

Test #13:

score: 0
Accepted
time: 2909ms
memory: 115916kb

input:

3000 2000
340027 415811 82817 134561 419447 365926 381133 23095 144595 26419 34153 489015 151446 273203 228955 325803 437286 326169 35163 295198 302964 309536 332477 53338 182205 51414 450400 365788 50804 13496 334250 251277 273738 492662 361508 127917 233762 227013 237730 443529 487736 322954 18598...

output:

509584529 505884467 509584529 505589821 509584529 509584529 509584529 509584529 509584529 509584529 506049235 509584529 505589821 509584529 509584529 509584529 509584529 509584529 509584529 505360737 507377470 508077499 509584529 509584529 506049235 509584529 509584529 509584529 509584529 509584529 ...

result:

ok 3000 numbers

Test #14:

score: 0
Accepted
time: 2082ms
memory: 116436kb

input:

3000 2000
206137 220133 435068 178537 171840 339613 183120 446132 304351 141963 327896 436271 200519 247836 188576 144642 382136 461780 251737 133930 317616 164059 139074 270029 105666 84338 470385 9315 171801 287588 202954 11523 175339 382980 85329 237447 419998 429600 443901 124176 212745 12478 66...

output:

571133130 570173848 571133130 571133130 570927492 571133130 570784784 571133130 571133130 571133130 571133130 571133130 571133130 571133130 571133130 571133130 571133130 571133130 571133130 570980418 571133130 571010547 571053023 571133130 570952154 570981184 571133130 571011107 571133130 571133130 ...

result:

ok 3000 numbers

Test #15:

score: 0
Accepted
time: 2996ms
memory: 116496kb

input:

3000 2000
167602 227995 73949 316919 35453 465010 159252 93563 30660 141993 164439 238021 226063 144110 377985 147061 304799 10143 19641 394140 163522 185753 428823 242903 135262 216536 39342 193425 444508 82866 444299 287346 223283 145380 358159 403817 78968 134156 160645 105261 365219 278415 32828...

output:

657721007 657721007 657632418 657721007 657593922 657721007 657717721 657652032 657589129 657700462 657721007 657721007 657721007 657702579 657721007 657705530 657721007 657568612 657578110 657721007 657721007 657721007 657721007 657721007 657693731 657721007 657597811 657721007 657721007 657641335 ...

result:

ok 3000 numbers

Test #16:

score: 0
Accepted
time: 2963ms
memory: 116032kb

input:

3000 2000
209838 400440 69515 246945 14065 238744 272504 250349 457341 61876 271742 467723 118571 425307 17908 436138 350652 342675 357624 410907 93802 107510 131252 97141 272943 49097 324356 107244 131904 42686 492428 426933 464408 350188 122836 308119 251571 466176 362646 202479 159161 94993 37618...

output:

617650977 617721673 617510654 617721673 617721673 617721673 617713643 617691488 617721673 617503015 617721673 617721673 617721673 617721673 617721673 617721673 617721673 617721673 617721673 617721673 617534941 617721673 617572391 617538280 617721673 617490236 617721673 617548383 617573043 617483825 ...

result:

ok 3000 numbers

Test #17:

score: 0
Accepted
time: 912ms
memory: 111084kb

input:

3000 2000
60585 40180 97784 242380 459972 255582 161564 131327 384022 481759 70533 421618 43784 15017 92423 225215 396505 418310 471415 151866 24081 220755 300977 175572 153728 73146 352475 53766 95108 311019 297452 99224 205533 298099 111705 436613 148366 74004 340456 299697 209998 168467 180979 99...

output:

529233344 529233344 529233344 526495802 529233344 528995372 529233344 529233344 529233344 529233344 527034133 529233344 529233344 528876395 528233185 529233344 529233344 529233344 529233344 528659338 529233344 527093416 528858160 529233344 527034133 527890886 529233344 529233344 528956126 529233344 ...

result:

ok 3000 numbers

Test #18:

score: 0
Accepted
time: 168ms
memory: 113292kb

input:

3000 2000
168963 196166 302361 33035 25174 212386 181263 43267 444394 285143 172124 81088 258830 476350 245387 195704 262555 138169 47086 462829 422185 70674 168505 475309 91517 125813 285313 181031 333565 235637 329045 446174 141699 125943 376815 339095 431684 300602 200899 401273 260987 298286 101...

output:

622026122 622053325 621957053 622081145 621885624 622069545 622038422 621993904 622081145 622081145 622081145 622056942 622081145 622081145 622081145 621833292 621976480 621995328 621904245 622081145 622081145 621927833 622081145 622081145 622081145 621794284 622081145 622038190 622081145 622081145 ...

result:

ok 3000 numbers

Test #19:

score: -100
Wrong Answer
time: 1039ms
memory: 1421836kb

input:

40000 2999
280266 433480 113244 331824 86713 245914 128246 405001 256101 23340 389100 256926 303281 266445 323768 296373 409059 371343 255536 248025 424647 219048 206559 335010 327166 475814 295615 288335 105522 469184 115059 369635 227372 146280 417304 97038 464567 379941 147916 450516 453399 41668...

output:

761199182 734466290 765341128 108852850 758007804 740250274 734228083 745886638 738474623 735781225 131359257 754658400 58217955 760685767 744884360 353151999 755270777 746450763 746340404 753189879 736861601 754404864 296779229 746012719 745646982 396139078 742743695 751337273 747950041 750693639 7...

result:

wrong answer 2nd numbers differ - expected: '748016221', found: '734466290'