QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#515775	#9159. 登山	Qwerty1232^#	0	4ms	3832kb	C++23	2.8kb	2024-08-12 02:17:06	2024-08-12 02:17:06

Judging History

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

[2024-08-12 02:17:06]
评测

测评结果：0
用时：4ms
内存：3832kb

查看

[2024-08-12 02:17:06]
提交

answer

#include <bits/stdc++.h>

constexpr int mod = 998'244'353;

int add(int a, int b) {
    return a + b - mod * (a + b >= mod);
}
void add_to(int& a, int b) {
    a = add(a, b);
}
int mul(int a, int b) {
    return a * 1ULL * b % mod;
}
int power(int b, int e) {
    int r = 1;
    for (; e > 0; e >>= 1) {
        if (e & 1)
            r = mul(r, b);
        b = mul(b, b);
    }
    return b;
}

struct ST {
    struct Data {
        int sum_val;
        int sum;

        Data(int val = 0) : sum_val(val), sum(0) { ; }
    };

    Data merge(Data a, const Data& b) const {
        add_to(a.sum, b.sum);
        add_to(a.sum_val, b.sum_val);
        return a;
    }

    std::vector<Data> data;
    int size;

    ST() = default;

    ST(int n) {
        data.assign(n, Data(0));
    }

    void add_val(int l, int r, int val) {
        for (int i = l; i < r; i++) {
            add_to(data[i].sum_val, val);
        }
    }

    void add_all() {
        for (int i = 0; i < data.size(); i++) {
            add_to(data[i].sum, data[i].sum_val);
        }
    }

    void clear(int l) {
        for (int i = l; i < data.size(); i++) {
            data[i] = Data(0);
        }
    }

    int get_sum(int i) {
        return data[i].sum;
    }

    void merge(const ST& other) {
        assert(other.data.size() == data.size());
        for (int i = 0; i < data.size(); i++) {
            data[i] = merge(data[i], other.data[i]);
        }
    }
};

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> prev(n, -1), max_depth(n, -1);
    std::vector<std::pair<int, int>> input(n);
    for (int i = 1; i < n; i++) {
        std::cin >> prev[i] >> input[i].first >> input[i].second >> max_depth[i];
        prev[i]--;
    }
    std::vector<int> depth(n);
    for (int i = 1; i < n; i++) {
        depth[i] = depth[prev[i]] + 1;
        max_depth[i] = depth[i] - max_depth[i] - 1;
    }
    std::vector<int> ord(n);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](int a, int b) { return depth[a] < depth[b]; });
    std::vector<int> dp(n, 0);
    dp[0] = 1;
    for (int i : ord) {
        for (int j = 1; j < n; j++) {
            if (depth[i] < depth[j] && depth[j] - input[j].second <= depth[i] && depth[i] <= depth[j] - input[j].first) {
                for (int t = j; max_depth[t] >= depth[i]; t = prev[t]) {
                    add_to(dp[t], dp[i]);
                }
            }
        }
    }

    for (int i = 1; i < n; i++) {
        std::cout << dp[i] << " \n"[i == n - 1];
    }
}

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int g, t;
    std::cin >> g >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 0

Wrong Answer

time: 0ms

memory: 3432kb

input:

output:

result:

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

Pretest #2:

score: 0

Wrong Answer

time: 3ms

memory: 3776kb

input:

output:

19 18 36 1 39 15 90 0 0 15 403 274 0 575 278 0 150 500 0 0 234 761 400 0 1053 0 385 871 256 2448 9925 4443 271 2798 1743 2690 38 310 1743 9269 20 0 215 0 20 1530 70455 28404 81025 50296 28044 6407 22124 52686 0 50506 25626 10848 607 3887 41288 41288 29804 1743 14432 25212 0 32979 84459 366626 356104...

result:

wrong answer 3rd numbers differ - expected: '35', found: '36'

Pretest #3:

score: 0

Wrong Answer

time: 3ms

memory: 3580kb

input:

output:

20 18 41 1 233 81 40 212 230 41 190 7469 58 0 6114 976 394 0 6095 7744 0 4869 4202 1355 33184 14745 1560 33145 4162 1 0 0 4162 242336 90131 122935 16079 39308 121458 4686 0 0 130647 70275 43122 39 40270 889894 37624 2646 148944 20929 54441 21784 0 5666 53569 0 38729 106899 77734 1067 0 1643 76214 0 ...

result:

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

Pretest #4:

score: 0

Time Limit Exceeded

input:

output:

1 1 28 87 25 31 114 117 1 83 21 0 31 21 287 141 708 578 2027 541 0 1875 635 52 709 231 394 20 7007 410 6317 5807 3713 0 15865 1978 15865 7750 1604 1604 41948 30 57510 30 54239 30 38590 0 8996 21844 0 269359 38953 229978 2245 28122 363285 388 98684 97695 297822 494589 288796 8622 20301 8740 2919 0 0 ...

result:

Pretest #5:

score: 0

Time Limit Exceeded

input:

output:

2 35 2 40 34 79 34 40 154 305 1490 1 0 1297 2823 725 261 2137 2098 261 1412 0 261 686 68 0 4757 4030 192 0 29 7322 2791 0 2598 0 0 2558 0 32945 14172 267 227 805 3247 2690 39630 21037 0 89370 89671 11354 60061 133958 23885 17225 121690 33748 118176 59509 3514 48856 78373 51873 3514 119772 100094 121...

result:

Pretest #6:

score: 0

Time Limit Exceeded

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

Time Limit Exceeded

input:

output:

result:

Pretest #8:

score: 0

Time Limit Exceeded

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

Time Limit Exceeded

input:

output:

result:

Pretest #10:

score: 0

Time Limit Exceeded

input:

output:

result:

Pretest #11:

score: 0

Time Limit Exceeded

input:

output:

result:

Pretest #12:

score: 0

Time Limit Exceeded

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

Time Limit Exceeded

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

Time Limit Exceeded

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

Time Limit Exceeded

input:

output:

result:

Pretest #16:

score: 0

Time Limit Exceeded

input:

output:

result:

Pretest #17:

score: 0

Time Limit Exceeded

input:

output:

result:

Pretest #18:

score: 0

Time Limit Exceeded

input:

output:

result:

Pretest #19:

score: 0

Time Limit Exceeded

input:

output:

result:

Pretest #20:

score: 0

Time Limit Exceeded

input:

output:

result:

Final Tests

Test #1:

score: 0

Wrong Answer

time: 0ms

memory: 3832kb

input:

output:

result:

wrong answer 9th numbers differ - expected: '2', found: '3'

Test #2:

score: 0

Wrong Answer

time: 4ms

memory: 3552kb

input:

output:

34 75 3 1 254 37 369 1 188 1397 28 990 39 1 75 5786 369 1 5748 38 1 1906 7627 8580 25543 991 16010 50511 38 8580 369 0 208 990 1 991 1 1086 0 0 93357 87365 8618 95 42846 331 15432 152942 0 0 622 135429 119997 20 314 0 622 229434 100984 488021 135146 2701517 50511 53888 1379825 30497 482974 733907 39...

result:

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

Test #3:

score: 0

Wrong Answer

time: 3ms

memory: 3632kb

input:

output:

25 249 447 129 26 274 1246 1 16 0 78 1288 26 275 25 52 173 763 1 2585 3974 1168 3253 1142 4767 5041 3253 0 8300 33784 35785 19648 823 7094 4046 14110 585 15124 160739 103928 5042 274 274 43619 144297 0 105719 0 5042 1211103 0 213470 514454 6759 0 6759 2585 219754 914074 106818 2710953 632766 277262 ...

result:

wrong answer 7th numbers differ - expected: '929', found: '1246'

Test #4:

score: 0

Time Limit Exceeded

input:

output:

3 2 1 90 41 1 40 177 126 125 315 34 46 177 270 844 33 33 2 45 178 33 8969 1014 46 7790 1701 0 0 5621 309 501 26946 13701 132 11262 26814 2538 101584 175841 0 79024 107423 6807 22455 0 40785 15644 22712 2998 0 0 21566 2998 257 2998 376 31839 0 132 751 0 19194 19194 0 107377 0 608044 53044 7322 753 25...

result:

Test #5:

score: 0

Time Limit Exceeded

input:

output:

34 33 0 6 70 0 5 1 4 32 82 41 41 0 304 0 303 575 230 262 107 41 254 575 1 2172 1 26 11193 7535 1383 5779 2121 153 4326 2672 1519 24 2835 653 24 20791 878 0 24 4398 4547 0 729 2025 47414 654 224 533 40 46960 641 88737 533 82713 5200 0 1513 11168 896 0 297002 9637 36048 102 1531 43069 26631 1531 31380...

result:

Test #6:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #7:

score: 0

Time Limit Exceeded

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

Time Limit Exceeded

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

Time Limit Exceeded

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

Time Limit Exceeded

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

Time Limit Exceeded

input:

output:

result:

Test #12:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #13:

score: 0

Time Limit Exceeded

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

Time Limit Exceeded

input:

output:

result:

Test #15:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #16:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #17:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #18:

score: 0

Time Limit Exceeded

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

Time Limit Exceeded

input:

output:

result:

Test #20:

score: 0

Time Limit Exceeded

input: