CSES - CEOI 2024, day 2

Submission details
Task:	Stations
Sender:	aatukaj
Submission time:	2025-03-03 16:14:13 +0200
Language:	C++ (C++17)
Status:	READY
Result:	37

Feedback
group	verdict	score
#1	WRONG ANSWER	0
#2	ACCEPTED	8
#3	WRONG ANSWER	0
#4	ACCEPTED	12
#5	ACCEPTED	17
#6	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	WRONG ANSWER	0.01 s	1, 6	details
#2	WRONG ANSWER	0.01 s	1, 6	details
#3	WRONG ANSWER	0.01 s	1, 6	details
#4	WRONG ANSWER	0.01 s	1, 3, 6	details
#5	ACCEPTED	0.01 s	1, 3, 6	details
#6	WRONG ANSWER	0.01 s	1, 3, 6	details
#7	WRONG ANSWER	0.01 s	1, 6	details
#8	WRONG ANSWER	0.01 s	1, 6	details
#9	WRONG ANSWER	0.01 s	1, 6	details
#10	WRONG ANSWER	0.01 s	1, 6	details
#11	WRONG ANSWER	0.01 s	1, 6	details
#12	WRONG ANSWER	0.01 s	1, 6	details
#13	ACCEPTED	0.01 s	1, 2, 3, 4, 5, 6	details
#14	ACCEPTED	0.09 s	2, 3, 4, 5, 6	details
#15	RUNTIME ERROR	0.06 s	3, 6	details
#16	RUNTIME ERROR	0.06 s	3, 6	details
#17	ACCEPTED	0.08 s	4, 5, 6	details
#18	ACCEPTED	0.09 s	3, 4, 5, 6	details
#19	ACCEPTED	0.10 s	3, 4, 5, 6	details
#20	ACCEPTED	0.01 s	1, 3, 4, 5, 6	details
#21	ACCEPTED	0.09 s	4, 5, 6	details
#22	ACCEPTED	0.09 s	4, 5, 6	details
#23	ACCEPTED	0.09 s	4, 5, 6	details
#24	ACCEPTED	0.07 s	5, 6	details
#25	ACCEPTED	0.08 s	5, 6	details
#26	ACCEPTED	0.08 s	5, 6	details
#27	ACCEPTED	0.08 s	5, 6	details
#28	ACCEPTED	0.08 s	5, 6	details
#29	ACCEPTED	0.08 s	5, 6	details
#30	ACCEPTED	0.05 s	5, 6	details
#31	RUNTIME ERROR	0.05 s	6	details
#32	RUNTIME ERROR	0.05 s	6	details
#33	RUNTIME ERROR	0.05 s	6	details
#34	RUNTIME ERROR	0.05 s	6	details
#35	RUNTIME ERROR	0.05 s	6	details
#36	RUNTIME ERROR	0.05 s	6	details
#37	RUNTIME ERROR	0.05 s	6	details
#38	RUNTIME ERROR	0.04 s	6	details

Code

#include <bits/stdc++.h>
using namespace std;

const int mxN = 7e4;
using pii = pair<int, int>;
using ll = long long;
vector<pair<int, ll>> adj[mxN];
int n;
ll k;
int sz[mxN];
ll ans[mxN];


int calc_sz(int v, int p) {
	sz[v] = 1;
	for (auto [u, _]: adj[v]) if (u!=p) sz[v] += calc_sz(u, v);
	return sz[v];
}
void dfs(int v, int p, ll dist) {
	for (auto [u, w]: adj[v]) if (u!=p) {
		ll new_dist = dist;
		if (dist+w>k) {
			ans[v]+=sz[u];
			new_dist = 0;
		}
		dfs(u, v, new_dist+w);
	}
}
void subtask1() {
	for (int i=0; i<n; i++) {
		calc_sz(i, -1);
		dfs(i, -1, 0);
	}
}
int dp[mxN][11];

int add_dp(int u, int v, int w, int sgn) {
	int cnt = 0;
	for (int i=0; i<=k-w; i++) {
		dp[v][i+w] += sgn*dp[u][i];
	}
	for (int i=k-w+1; i<=k; i++) {
		cnt += dp[u][i];
	}
	dp[v][w] += sgn*cnt;
	return cnt;

}

void dfs1(int v, int p) {
	dp[v][0] = 1;
	for (auto [u, w]: adj[v]) if (u!=p) {
		dfs1(u, v);
		int cnt = add_dp(u, v, w, 1);
		ans[u] += 1ll*(n-sz[u])*cnt; 
	}

}
void dfs2(int v, int p) {
	for (auto [u, w]: adj[v]) if (u!=p) {
		add_dp(u, v, w, -1);
		int cnt = 0;
		for (int i=0; i<=k-w; i++) {
			dp[u][i+w] += dp[v][i];
		}
		for (int i=k-w+1; i<=k; i++) {
			cnt += dp[v][i];
		}
		dp[u][w] += cnt;
		ans[v] += 1ll*(sz[u])*cnt;
		dfs2(u,v );

		for (int i=0; i<=k-w; i++) {
			dp[u][i+w] -= dp[v][i];
		}
		dp[u][w] -= cnt;
		add_dp(u, v, w, 1);
	}
}



void subtask5() {
	calc_sz(0, -1);
	dfs1(0, -1);
	//cout << "FIRST DONE" << endl;
	dfs2(0, -1);
}


void solve() {
	cin >> n >> k;
	for (int i=0; i<n-1; i++) {
		int u, v, w;
		cin >> u >> v >> w;	
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	if (n<=1) subtask1();
	else subtask5();
	for (int i=0; i<n; i++) cout << ans[i] << ' ';
	cout << '\n';
} 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
}

Test details

Test 1

Group: 1, 6

Verdict: WRONG ANSWER

input
`750 918 159 63 18 573 310 105 135 400 57 618 27 113 ...` view save

correct output
`0 96 45 94 0 ...` view save

user output
`344007840 1187646283 379453952...` Truncated

Test 2

Group: 1, 6

Verdict: WRONG ANSWER

input
`967 334 285 176 1 648 431 1 493 893 2 261 165 1 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`59130781661 11523451368 -17776...` Truncated

Test 3

Group: 1, 6

Verdict: WRONG ANSWER

input
`1000 963 408 385 876 23 519 951 649 232 605 821 385 792 ...` view save

correct output
`0 0 482612 0 912 ...` view save

user output
`547249947255 1235306967489 -11...` Truncated

Test 4

Group: 1, 3, 6

Verdict: WRONG ANSWER

input
`1000 396 412 257 190 290 965 25 399 938 174 980 459 117 ...` view save

correct output
`215160 138947 196491 47632 103775 ...` view save

user output
`847641521997 -910820571291 -11...` Truncated

Test 5

Group: 1, 3, 6

Verdict: ACCEPTED

input
`1000 333 896 853 0 28 756 0 658 183 0 488 17 0 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...` Truncated

Test 6

Group: 1, 3, 6

Verdict: WRONG ANSWER

input
`2 31 0 1 31` view save

correct output
`0 0` view save

user output
`1 1` view save

Test 7

Group: 1, 6

Verdict: WRONG ANSWER

input
`1000 847 24 298 474 208 141 485 789 89 60 1 809 437 ...` view save

correct output
`16 1080 1966 5980 1856 ...` view save

user output
`740850409689 -1391970499575 47...` Truncated

Test 8

Group: 1, 6

Verdict: WRONG ANSWER

input
`1000 767 476 799 361 271 239 215 447 941 269 219 664 600 ...` view save

correct output
`1017 997 3988 1996 0 ...` view save

user output
`2104368427244 -1477379095030 -...` Truncated

Test 9

Group: 1, 6

Verdict: WRONG ANSWER

input
`1000 1000 574 351 479 444 634 559 531 70 113 180 828 194 ...` view save

correct output
`17839 4922 3988 0 0 ...` view save

user output
`1738153501371 1372477297827 -1...` Truncated

Test 10

Group: 1, 6

Verdict: WRONG ANSWER

input
`1000 1000 680 881 340 73 368 929 303 239 219 861 605 561 ...` view save

correct output
`88 3990 9954 0 0 ...` view save

user output
`-872417429012 1303681747910 26...` Truncated

Test 11

Group: 1, 6

Verdict: WRONG ANSWER

input
`1000 1000 164 378 963 934 141 358 866 915 598 341 220 55 ...` view save

correct output
`1996 0 1147 1996 18739 ...` view save

user output
`1607039705496 256565178 954917...` Truncated

Test 12

Group: 1, 6

Verdict: WRONG ANSWER

input
`1000 537 276 155 470 533 155 391 175 155 343 553 155 270 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`20979 23976 23976 2997 999 339...` Truncated

Test 13

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
`2 1 0 1 1` view save

correct output
`0 0` view save

user output
`0 0` view save

Test 14

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
`70000 1 50913 18377 1 33894 11911 1 61940 7863 1 61602 33470 1 ...` view save

correct output
`2128187656 1918647796 1539693556 1198079316 2227641388 ...` view save

user output
`2128187656 1918647796 15396935...` Truncated

Test 15

Group: 3, 6

Verdict: RUNTIME ERROR

input
`70000 517272873 57335 18148 62837135 28239 56484 253183094 23004 59130 129215861 558 17489 52424960 ...` view save

correct output
`450859 215263283 544492560 222149 1276050 ...` view save

user output
(empty)

Test 16

Group: 3, 6

Verdict: RUNTIME ERROR

input
`70000 611016790 21272 16063 50360 30758 33429 30642 23317 5625 9045 66335 5731 24130 ...` view save

correct output
`69999 102210 23584 30220 0 ...` view save

user output
(empty)

Test 17

Group: 4, 5, 6

Verdict: ACCEPTED

input
`69973 4 44281 27162 1 15299 61302 1 19250 66379 1 45970 65938 1 ...` view save

correct output
`769608 34960 1162375 626228 2 ...` view save

user output
`769608 34960 1162375 626228 2 ...` Truncated

Test 18

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
`70000 6 12580 20937 2 31244 33335 1 62095 66946 0 2558 64306 2 ...` view save

correct output
`95678 275287413 81937227 47960445 176569 ...` view save

user output
`95678 275287413 81937227 47960...` Truncated

Test 19

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
`70000 10 45546 20793 0 44801 49720 0 54732 9736 0 64375 18647 0 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...` Truncated

Test 20

Group: 1, 3, 4, 5, 6

Verdict: ACCEPTED

input
`2 6 0 1 6` view save

correct output
`0 0` view save

user output
`0 0` view save

Test 21

Group: 4, 5, 6

Verdict: ACCEPTED

input
`70000 10 36906 67900 2 51465 24882 0 65531 32406 0 49018 50640 10 ...` view save

correct output
`0 0 1141061037 69997 0 ...` view save

user output
`0 0 1141061037 69997 0 0 41998...` Truncated

Test 22

Group: 4, 5, 6

Verdict: ACCEPTED

input
`70000 10 40966 26929 6 15381 7596 3 53090 61576 3 6976 65087 2 ...` view save

correct output
`279988 0 0 56174160 0 ...` view save

user output
`279988 0 0 56174160 0 0 233238...` Truncated

Test 23

Group: 4, 5, 6

Verdict: ACCEPTED

input
`70000 10 47111 32841 10 510 5994 10 1362 44478 8 61688 30984 5 ...` view save

correct output
`419980 0 979765 0 1679710 ...` view save

user output
`419980 0 979765 0 1679710 1399...` Truncated

Test 24

Group: 5, 6

Verdict: ACCEPTED

input
`70000 7 12257 45873 7 53771 24407 7 67182 59338 2 68981 59097 6 ...` view save

correct output
`0 0 0 0 56749 ...` view save

user output
`0 0 0 0 56749 139996 0 0 22732...` Truncated

Test 25

Group: 5, 6

Verdict: ACCEPTED

input
`70000 7 60987 29710 2 40235 14667 3 49803 36218 0 1256 23603 0 ...` view save

correct output
`559942 0 69996 0 0 ...` view save

user output
`559942 0 69996 0 0 139996 0 0 ...` Truncated

Test 26

Group: 5, 6

Verdict: ACCEPTED

input
`70000 4 29827 12474 3 52717 68608 1 26411 5022 3 66140 68360 2 ...` view save

correct output
`419970 0 0 202 0 ...` view save

user output
`419970 0 0 202 0 0 279984 0 0 ...` Truncated

Test 27

Group: 5, 6

Verdict: ACCEPTED

input
`70000 10 41642 65096 7 14235 28073 6 48132 705 7 23384 33897 0 ...` view save

correct output
`139996 279988 0 0 0 ...` view save

user output
`139996 279988 0 0 0 1399787 0 ...` Truncated

Test 28

Group: 5, 6

Verdict: ACCEPTED

input
`70000 10 44002 46661 10 16351 40057 10 62342 69569 2 277 38372 1 ...` view save

correct output
`0 0 559966 0 0 ...` view save

user output
`0 0 559966 0 0 0 0 1259820 769...` Truncated

Test 29

Group: 5, 6

Verdict: ACCEPTED

input
`70000 10 11173 32861 3 13926 50906 10 18305 60850 3 13279 836 9 ...` view save

correct output
`0 139996 2 0 0 ...` view save

user output
`0 139996 2 0 0 0 139994 0 1557...` Truncated

Test 30

Group: 5, 6

Verdict: ACCEPTED

input
`70000 3 18748 12670 2 56209 12670 2 4918 12670 1 26713 12670 2 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...` Truncated

Test 31

Group: 6

Verdict: RUNTIME ERROR

input
`67845 886519666 14071 38244 390226 23927 10508 4649507 24776 60617 7933069 44979 29276 6727041 ...` view save

correct output
`43 0 395 0 81 ...` view save

user output
(empty)

Test 32

Group: 6

Verdict: RUNTIME ERROR

input
`70000 598182175 35387 18369 177725639 34272 27820 390474503 14996 60451 566274308 31897 35730 516503530 ...` view save

correct output
`0 0 0 2373343036 2449703732 ...` view save

user output
(empty)

Test 33

Group: 6

Verdict: RUNTIME ERROR

input
`70000 307114024 18 68382 208881990 51105 51287 133487858 6935 48425 203987749 30063 35675 238707761 ...` view save

correct output
`0 5457705 0 420055 0 ...` view save

user output
(empty)

Test 34

Group: 6

Verdict: RUNTIME ERROR

input
`70000 260495634 10465 32381 229572819 59714 8684 92922283 44269 63680 232833764 47600 15978 126514599 ...` view save

correct output
`350035 839810 1 0 477281 ...` view save

user output
(empty)

Test 35

Group: 6

Verdict: RUNTIME ERROR

input
`70000 1000000000 40606 60962 166792 66689 16700 510579 39392 42623 271902 12827 150 783709 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

Test 36

Group: 6

Verdict: RUNTIME ERROR

input
`70000 1000000000 18028 63559 764765 43037 44898 469661 22315 22254 359926 32987 69384 314936 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

Test 37

Group: 6

Verdict: RUNTIME ERROR

input
`70000 1000000000 48195 15915 457746 7436 2784 442186 9122 3611 587852 31354 12943 476363 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

Test 38

Group: 6

Verdict: RUNTIME ERROR

input
`70000 852351984 54341 29527 743304598 55902 29527 379127182 8584 29527 326761145 21272 29527 850588761 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

CEOI 2024, day 2

Stations

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Tasks

Submissions (aatukaj)