QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#510444	#9159. 登山	Insert_Username_Here^#	0	128ms	199808kb	C++20	1.3kb	2024-08-09 04:42:41	2024-08-09 04:42:42

Judging History

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

[2024-08-09 04:42:42]
评测

测评结果：0
用时：128ms
内存：199808kb

查看

[2024-08-09 04:42:41]
提交

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) {
	for(ll j = 0; j < n; j++) dp[i][j] = 0;
	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];
		for(ll k = l[i]; k <= r[i]; k++) {
			if(d[i] - d[par] > h[i]) dp[i][par] = (dp[i][par] + dp[j][par]) % mod;
			par = p[par];
		}
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll c, t;
	cin >> c >> t;
	ans[0] = 1;
	while(t--) {
		cin >> n;
		adj[0].clear();
		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);
			adj[i].clear();
		}
		dfs(0);
		for(ll i = 1; i < n; i++) {
			ll par = lp[i];
			ans[i] = 0;
			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: 3632kb

input:

output:

result:

wrong answer 17th numbers differ - expected: '2', found: '1'

Pretest #2:

score: 0

Wrong Answer

time: 0ms

memory: 16052kb

input:

output:

4 3 5 1 8 0 5 0 0 0 13 0 0 5 20 0 10 8 0 0 13 5 0 0 13 0 11 8 10 5 37 13 19 24 26 47 7 0 26 55 4 0 0 0 4 18 292 58 203 20 121 0 66 26 0 200 98 23 0 0 0 211 58 26 103 105 0 176 464 720 920 0 0 0 174 452 951 833 819 0 390 507 476 679 852 749 0 18 0 489 148 26 0 4769 0 25 249 3963 402 0 1151 5 36 0 0 1...

result:

wrong answer 1st numbers differ - expected: '19', found: '4'

Pretest #3:

score: 0

Wrong Answer

time: 2ms

memory: 14184kb

input:

output:

10 8 2 1 13 30 19 2 29 11 10 62 16 0 16 63 48 0 71 84 0 23 0 23 18 87 73 243 0 1 0 0 0 738 18 512 132 256 517 23 0 0 427 281 211 18 0 1746 257 0 889 171 295 330 0 180 256 0 364 439 54 0 0 0 261 0 0 21 0 999 261 556 738 0 1219 0 594 706 306 706 0 261 0 0 388 0 280 1327 204 855 2351 6712 3509 0 724 0 ...

result:

wrong answer 1st numbers differ - expected: '20', found: '10'

Pretest #4:

score: 0

Wrong Answer

time: 128ms

memory: 199764kb

input:

output:

1 1 4 11 1 5 12 15 1 10 0 0 5 0 13 0 4 32 40 39 0 104 40 0 34 12 24 0 170 0 68 38 4 0 0 24 403 206 0 0 22 0 448 0 663 4 264 0 228 0 0 0 320 1537 38 83 1757 22 38 0 41 79 2213 229 471 245 13 0 0 1811 1111 5 0 1947 400 0 264 0 414 0 0 538 744 0 2165 38 448 0 0 0 0 0 456 0 414 0 0 0 38 2005 372 264 546...

result:

wrong answer 3rd numbers differ - expected: '28', found: '4'

Pretest #5:

score: 0

Wrong Answer

time: 128ms

memory: 199764kb

input:

output:

2 1 1 3 0 2 1 2 0 2 2 1 0 0 3 4 0 1 9 0 8 0 2 3 0 0 10 0 1 0 0 6 6 0 4 0 0 8 0 12 7 3 1 0 4 3 14 2 0 13 29 4 8 20 10 7 7 12 2 22 0 0 25 12 7 0 32 0 6 2 0 0 0 0 25 2 0 9 74 90 8 0 7 113 0 20 0 19 72 10 0 17 0 0 0 0 0 7 0 49 6 0 0 0 44 0 111 5 0 0 106 0 0 30 0 353 106 44 0 0 0 281 12 0 600 0 0 325 320...

result:

wrong answer 2nd numbers differ - expected: '35', found: '1'

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: 0ms

memory: 3700kb

input:

output:

result:

wrong answer 1st numbers differ - expected: '4', found: '3'

Test #2:

score: 0

Wrong Answer

time: 3ms

memory: 15984kb

input:

output:

5 10 3 1 4 5 16 1 0 23 3 9 6 0 10 11 10 1 33 5 0 14 11 18 22 4 45 79 0 18 0 0 25 12 0 10 0 24 0 0 110 70 24 11 55 4 56 178 0 0 0 148 92 1 0 0 3 66 0 356 191 676 79 66 726 57 373 150 42 0 7 35 69 0 51 371 395 20 47 371 48 1 214 90 33 57 371 0 284 357 12 0 0 1600 0 135 149 0 2470 174 490 1271 477 127 ...

result:

wrong answer 1st numbers differ - expected: '34', found: '5'

Test #3:

score: 0

Wrong Answer

time: 0ms

memory: 16196kb

input:

output:

5 39 67 15 6 44 133 0 1 0 6 78 6 45 5 0 1 0 1 85 0 1 0 121 146 265 0 0 742 571 634 185 0 269 79 380 0 438 0 1376 191 44 44 1122 1039 0 106 0 191 3290 0 1645 234 0 0 0 0 1992 158 1484 6874 2869 0 269 1376 1645 370 1567 0 2226 185 11 8324 12662 6314 742 6158 2302 190 634 5338 0 0 0 7798 2790 45 4435 0...

result:

wrong answer 1st numbers differ - expected: '25', found: '5'

Test #4:

score: 0

Wrong Answer

time: 117ms

memory: 199808kb

input:

output:

3 2 1 2 3 1 2 3 1 6 12 1 4 5 9 23 0 0 2 3 6 0 13 7 4 0 1 0 0 7 7 0 2 24 2 23 3 10 54 58 0 9 39 13 0 0 33 27 9 0 0 0 0 0 0 13 0 26 0 2 0 0 0 0 0 77 0 141 58 7 0 0 2 126 0 14 45 0 23 18 27 0 0 7 10 30 0 43 0 0 22 21 0 84 21 0 0 273 83 42 278 21 48 0 0 42 0 34 210 85 1208 0 843 0 0 284 0 0 139 86 43 91...

result:

wrong answer 5th numbers differ - expected: '41', found: '3'

Test #5:

score: 0

Wrong Answer

time: 123ms

memory: 199672kb

input:

output:

2 1 0 1 1 0 0 1 4 2 4 2 2 0 1 0 0 3 8 8 3 3 0 4 0 18 1 0 6 13 7 16 16 4 13 17 11 0 8 7 0 35 0 0 0 11 11 0 2 0 3 8 0 0 2 22 11 108 8 67 18 0 8 7 11 0 186 0 33 0 0 12 6 7 28 15 183 8 11 76 0 178 15 19 16 4 385 37 3 43 384 5 34 0 0 0 7 0 0 1 415 11 412 6 0 70 212 186 0 0 211 420 8 0 44 776 529 8 208 12...

result:

wrong answer 1st numbers differ - expected: '34', found: '2'

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: