QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#510447	#9159. 登山	Insert_Username_Here^#	0	157ms	199780kb	C++20	1.3kb	2024-08-09 04:51:20	2024-08-09 04:51:20

Judging History

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

[2024-08-09 04:51:20]
评测

测评结果：0
用时：157ms
内存：199780kb

查看

[2024-08-09 04:51:20]
提交

answer

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll mod = 998244353;
// cope counter = 2254

const ll N = 5001;
ll n;
vector<ll> adj[N];
ll d[N], p[N], lp[N], l[N], r[N], h[N], dp[N][N], ans[N];
void dfs(ll i) {
	ll par = lp[i];
	for(ll j = l[i]; j <= r[i]; j++) {
		if(d[i] - d[par] > h[i]) dp[i][par] = 1;
		par = p[par];
	}
	for(ll j : adj[i]) {
		dfs(j);
		par = lp[i];
		while(1) {
			if(d[i] - d[par] > h[i]) dp[i][par] = (dp[i][par] + dp[j][par]) % mod;
			if(!par) break;
			par = p[par];
		}
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll c, t;
	cin >> c >> t;
	while(t--) {
		cin >> n;
		for(int i = 0; i < n; i++) {
			adj[i].clear();
			ans[i] = 0;
			for(int j = 0; j < n; j++) dp[i][j] = 0;
		}
		for(ll i = 1; i < n; i++) {
			cin >> p[i] >> l[i] >> r[i] >> h[i], p[i]--;
			lp[i] = i;
			for(ll j = 0; j < l[i]; j++) lp[i] = p[lp[i]];
			d[i] = d[p[i]] + 1;
			adj[p[i]].push_back(i);
		}
		dfs(0);
		ans[0] = 1;
		for(ll i = 1; i < n; i++) {
			ll par = lp[i];
			for(ll j = l[i]; j <= r[i]; j++) {
				ans[i] = (ans[i] + ans[par] * dp[i][par]) % mod;
				par = p[par];
			}
		}
		for(ll i = 1; i < n; i++) cout << ans[i] << " ";
		cout << "\n";
	}
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 0

Wrong Answer

time: 0ms

memory: 3668kb

input:

output:

result:

wrong answer 18th numbers differ - expected: '5', found: '4'

Pretest #2:

score: 0

Wrong Answer

time: 3ms

memory: 15968kb

input:

output:

19 18 35 1 38 0 35 0 0 0 334 0 0 35 110 0 40 490 0 0 73 105 0 0 334 0 378 426 70 105 1568 595 109 320 422 1059 37 0 422 1803 19 0 0 0 19 369 8257 1091 5737 355 3542 0 1878 3407 0 6254 3392 2723 0 0 0 7192 2016 422 2962 3966 0 5345 14298 22389 26095 0 0 0 6672 36061 29537 22759 52631 0 16281 15965 14...

result:

wrong answer 6th numbers differ - expected: '15', found: '0'

Pretest #3:

score: 0

Wrong Answer

time: 0ms

memory: 14340kb

input:

output:

20 18 2 1 33 80 39 12 229 41 180 396 36 0 270 313 118 0 566 589 0 243 0 126 280 836 493 2001 0 1 0 0 0 8768 280 4128 1120 2064 4345 528 0 0 3928 3340 2540 38 0 18092 2213 0 7449 1425 2473 2692 0 1534 2064 0 3050 3679 454 0 0 0 2281 0 0 51 0 11049 2281 4754 8768 0 10141 0 4834 6520 2314 6520 0 2281 0...

result:

wrong answer 3rd numbers differ - expected: '40', found: '2'

Pretest #4:

score: 0

Wrong Answer

time: 152ms

memory: 199780kb

input:

output:

1 1 28 83 25 29 84 111 1 79 0 0 29 0 109 0 125 272 488 300 0 902 304 0 247 84 192 0 1678 0 813 917 125 0 0 1048 3824 1954 0 0 1981 0 3694 0 8118 28 2393 0 2117 0 0 0 4347 18598 396 2992 20378 163 1898 0 1599 3497 24899 2142 4863 2254 579 0 0 21544 11812 29 0 23357 4680 0 2393 0 14096 0 0 6207 7014 0...

result:

wrong answer 7th numbers differ - expected: '108', found: '84'

Pretest #5:

score: 0

Wrong Answer

time: 157ms

memory: 199764kb

input:

output:

2 35 2 3 0 4 34 3 0 245 242 1 0 0 279 314 0 70 837 0 594 0 100 279 0 0 907 0 35 0 0 556 869 0 833 0 0 1423 0 1802 621 70 34 0 487 374 3035 100 0 3240 3946 342 2205 5210 1702 557 4022 1802 200 3251 0 0 3746 1802 557 0 5453 0 556 36 0 0 0 0 3746 200 0 1284 18907 18431 684 0 5310 24655 0 4689 0 4779 18...

result:

wrong answer 5th numbers differ - expected: '34', found: '0'

Pretest #6:

score: 0

Runtime Error

input:

6
4
100000
1 1 1 0
2 1 1 0
3 1 1 0
4 2 2 0
5 1 1 0
6 2 2 0
7 6 6 0
8 3 3 0
9 6 6 0
10 8 8 0
11 6 6 0
12 12 12 0
13 11 11 0
14 2 2 0
15 2 2 0
16 2 2 0
17 9 9 0
18 1 1 0
19 4 4 0
20 18 18 0
21 13 13 0
22 20 20 0
23 3 3 0
24 21 21 0
25 8 8 0
26 11 11 0
27 11 11 0
28 3 3 0
29 21 21 0
30 1 1 0
31 27 27 0...

output:

result:

Pretest #7:

score: 0

Runtime Error

input:

output:

result:

Pretest #8:

score: 0

Runtime Error

input:

8
4
100000
1 1 1 0
2 2 2 0
3 3 3 0
4 4 4 2
5 2 2 1
6 6 6 0
7 2 2 0
8 7 7 3
9 4 4 3
10 1 1 4
11 3 3 0
12 8 8 11
13 13 13 7
14 5 5 10
15 8 8 11
16 14 14 5
17 9 9 2
18 17 17 7
19 3 3 1
20 1 1 9
21 14 14 5
22 5 5 17
23 8 8 14
24 8 8 9
25 24 24 7
26 24 24 7
27 17 17 8
28 27 27 27
29 26 26 6
30 17 17 14
3...

output:

result:

Pretest #9:

score: 0

Runtime Error

input:

output:

result:

Pretest #10:

score: 0

Runtime Error

input:

output:

result:

Pretest #11:

score: 0

Runtime Error

input:

output:

result:

Pretest #12:

score: 0

Runtime Error

input:

12
4
100000
1 1 1 0
1 1 1 0
3 1 2 0
3 1 2 0
4 1 1 0
4 1 3 0
6 2 4 0
7 2 4 0
9 1 4 0
8 1 3 0
11 3 3 0
11 5 6 0
12 1 2 0
14 3 3 0
13 2 7 0
16 2 3 0
17 2 4 0
17 7 9 0
17 3 8 0
20 2 6 0
21 10 11 0
21 6 11 0
21 7 9 0
23 3 4 0
24 5 11 0
26 6 9 0
26 5 7 0
27 12 13 0
29 10 10 0
28 1 3 0
31 13 15 0
32 7 13 0...

output:

result:

Pretest #13:

score: 0

Runtime Error

input:

13
4
100000
1 1 1 0
2 1 2 0
3 2 2 2
4 2 4 1
5 1 2 4
6 4 6 2
7 1 6 4
8 6 6 5
9 5 8 8
10 6 6 1
11 8 11 5
12 8 11 1
13 4 8 6
14 4 7 1
15 11 15 5
16 1 1 10
17 6 9 7
18 8 16 2
19 2 9 10
20 6 20 7
21 12 14 11
22 9 14 14
23 6 7 22
24 12 14 11
25 20 20 21
26 10 20 0
27 19 26 8
28 21 23 12
29 4 13 23
30 15 2...

output:

result:

Pretest #14:

score: 0

Runtime Error

input:

14
4
100000
1 1 1 0
2 1 1 1
1 1 1 0
2 1 2 1
4 2 2 1
5 2 2 1
7 1 4 1
8 2 5 3
8 5 5 3
10 2 3 5
11 1 6 5
10 1 4 5
12 5 8 1
12 3 6 5
13 3 6 2
15 2 5 8
17 6 7 6
18 6 8 5
17 10 10 1
18 4 5 5
20 4 11 7
22 8 9 4
23 9 13 12
24 9 13 10
24 6 8 7
26 3 13 13
26 11 14 11
28 11 11 2
27 9 16 8
30 6 12 0
31 13 17 16...

output:

result:

Pretest #15:

score: 0

Runtime Error

input:

output:

result:

Pretest #16:

score: 0

Runtime Error

input:

output:

result:

Pretest #17:

score: 0

Runtime Error

input:

output:

result:

Pretest #18:

score: 0

Runtime Error

input:

output:

result:

Pretest #19:

score: 0

Runtime Error

input:

output:

result:

Pretest #20:

score: 0

Runtime Error

input:

output:

result:

Final Tests

Test #1:

score: 0

Wrong Answer

time: 1ms

memory: 3692kb

input:

output:

result:

wrong answer 4th numbers differ - expected: '1', found: '0'

Test #2:

score: 0

Wrong Answer

time: 3ms

memory: 16136kb

input:

output:

34 68 3 1 32 34 103 1 0 166 28 66 36 0 68 332 67 1 496 34 0 120 332 392 184 32 327 1107 0 392 0 0 170 94 0 67 0 184 0 0 1360 497 427 89 680 32 922 1850 0 0 0 1603 681 20 0 0 28 3472 0 3692 2471 6682 1107 1824 7253 1779 3573 1989 1246 0 420 273 1040 0 1776 5191 7140 134 856 7609 368 40 2143 1419 496 ...

result:

wrong answer 2nd numbers differ - expected: '69', found: '68'

Test #3:

score: 0

Wrong Answer

time: 0ms

memory: 18256kb

input:

output:

25 224 397 100 26 249 800 0 16 0 53 448 26 250 25 0 16 0 1 475 0 1 0 721 861 1599 0 0 5019 3332 3719 1085 0 2149 464 2220 0 2583 0 8738 1111 249 249 7239 9026 0 2362 0 1111 21774 0 10887 1344 0 0 0 0 13484 928 10038 52204 20998 0 2149 8738 10887 5201 9849 0 15057 1085 458 57850 96517 45393 5019 4494...

result:

wrong answer 2nd numbers differ - expected: '249', found: '224'

Test #4:

score: 0

Wrong Answer

time: 148ms

memory: 199724kb

input:

output:

3 2 1 2 41 1 40 3 36 82 164 34 42 81 123 289 0 0 2 41 82 0 3313 118 42 0 34 0 0 2925 121 0 760 846 40 1138 102 192 4909 14228 0 3685 7334 715 0 0 9551 3896 1816 0 0 0 0 0 0 349 0 6604 0 40 0 0 0 0 0 8414 0 16771 6035 2925 0 0 2 28215 0 234 8803 0 3505 316 9163 0 0 2272 192 9288 0 12601 0 0 6998 7472...

result:

wrong answer 9th numbers differ - expected: '118', found: '36'

Test #5:

score: 0

Wrong Answer

time: 144ms

memory: 199688kb

input:

output:

34 33 0 6 33 0 0 1 4 32 14 7 7 0 31 0 0 65 18 197 95 35 0 96 0 455 1 0 724 352 162 450 394 100 453 418 292 0 258 163 0 1604 0 0 0 292 292 0 66 0 130 164 0 0 34 1118 292 4338 197 2764 455 0 197 611 292 0 7429 0 1410 0 0 655 724 163 1308 1583 7299 264 292 2500 0 7232 1195 484 421 96 17264 2696 130 225...

result:

wrong answer 5th numbers differ - expected: '65', found: '33'

Test #6:

score: 0

Runtime Error

input:

output:

result:

Test #7:

score: 0

Runtime Error

input:

7
4
100000
1 1 1 0
1 1 1 0
1 1 1 0
1 1 1 0
5 2 2 0
5 2 2 0
7 1 1 0
8 1 1 0
6 1 1 0
7 3 3 0
9 3 3 0
12 2 2 0
10 2 2 0
13 1 1 0
13 4 4 0
13 7 7 0
15 1 1 0
15 7 7 0
16 7 7 0
19 1 1 0
18 8 8 0
19 2 2 0
23 1 1 0
23 5 5 0
24 8 8 0
23 6 6 0
27 3 3 0
28 4 4 0
26 12 12 0
29 6 6 0
30 1 1 0
31 12 12 0
30 9 9 0...

output:

result:

Test #8:

score: 0

Runtime Error

input:

8
4
100000
1 1 1 0
2 2 2 0
3 2 2 1
4 2 2 2
5 3 3 0
6 6 6 2
7 1 1 6
8 8 8 2
9 1 1 6
10 2 2 3
11 4 4 2
12 6 6 5
13 2 2 11
14 1 1 6
15 7 7 4
16 7 7 3
17 14 14 15
18 12 12 12
19 17 17 3
20 20 20 11
21 5 5 7
22 12 12 3
23 14 14 10
24 3 3 1
25 23 23 10
26 5 5 18
27 5 5 25
28 18 18 1
29 2 2 14
30 23 23 3
3...

output:

result:

Test #9:

score: 0

Runtime Error

input:

9
4
100000
1 1 1 0
1 1 1 0
1 1 1 0
3 1 1 0
4 2 2 1
6 2 2 2
6 1 1 2
8 3 3 2
9 1 1 4
8 4 4 0
9 4 4 0
12 6 6 3
13 3 3 4
13 6 6 3
15 5 5 0
15 2 2 7
15 4 4 2
17 5 5 2
18 5 5 0
18 4 4 6
19 2 2 8
22 8 8 9
23 3 3 10
24 6 6 12
25 7 7 13
24 1 1 11
27 3 3 7
27 12 12 2
28 4 4 0
30 3 3 9
31 15 15 15
32 1 1 7
31 ...

output:

result:

Test #10:

score: 0

Runtime Error

input:

10
4
100000
1 1 1 0
2 1 1 0
3 3 3 0
4 3 4 0
5 3 5 0
6 1 4 0
7 5 5 0
8 5 7 0
9 3 6 0
10 6 10 0
11 1 2 0
12 8 11 0
13 4 12 0
14 2 12 0
15 7 10 0
16 6 8 0
17 13 15 0
18 8 9 0
19 2 6 0
20 8 14 0
21 3 18 0
22 11 18 0
23 5 11 0
24 6 12 0
25 3 24 0
26 13 23 0
27 3 8 0
28 14 22 0
29 4 26 0
30 1 5 0
31 13 17...

output:

result:

Test #11:

score: 0

Runtime Error

input:

output:

result:

Test #12:

score: 0

Runtime Error

input:

output:

result:

Test #13:

score: 0

Runtime Error

input:

13
4
100000
1 1 1 0
2 1 2 1
3 1 2 2
4 1 3 2
5 1 5 4
6 1 4 4
7 6 6 1
8 3 7 5
9 3 4 4
10 5 6 2
11 6 9 4
12 5 11 9
13 1 3 4
14 6 10 10
15 4 6 8
16 3 8 6
17 1 9 3
18 3 13 8
19 3 11 10
20 2 4 11
21 12 13 0
22 13 17 20
23 9 17 1
24 10 11 16
25 22 25 9
26 5 9 4
27 12 27 26
28 13 13 22
29 8 23 1
30 21 23 19...

output:

result:

Test #14:

score: 0

Runtime Error

input:

output:

result:

Test #15:

score: 0

Runtime Error

input:

output:

result:

Test #16:

score: 0

Runtime Error

input:

output:

result:

Test #17:

score: 0

Runtime Error

input:

output:

result:

Test #18:

score: 0

Runtime Error

input:

18
4
100000
1 1 1 0
1 1 1 0
3 1 2 1
2 1 2 0
2 2 2 0
5 1 3 1
6 1 1 1
6 2 3 2
6 1 3 2
9 1 4 1
10 2 3 1
12 1 3 0
10 1 4 2
11 2 5 0
12 4 5 1
14 2 4 1
15 5 6 2
16 4 5 5
18 3 3 5
18 1 6 4
18 3 4 4
21 2 4 3
21 4 7 4
23 7 9 3
23 1 5 3
25 3 5 3
26 5 6 2
25 1 7 4
29 3 4 6
30 4 11 2
29 1 3 3
29 1 5 6
32 9 12 0...

output:

result:

Test #19:

score: 0

Runtime Error

input:

output:

result:

Test #20:

score: 0

Runtime Error

input: