oj.uz

Submission #894066

# Submission time Handle Problem Language Result Execution time Memory
894066 2023-12-27T23:35:14 Z juliany2 Sprinkler (JOI22_sprinkler) C++17
100 / 100
 871 ms 101912 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 2e5 + 7, D = 45;
int n, mod;
vector<int> adj[N];
int p[N];
ll h[N], lz[N][D];

void dfs(int v = 1) {
    for (int u : adj[v]) {
        if (u != p[v]) {
            p[u] = v;
            dfs(u);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> mod;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++)
        cin >> h[i];

    dfs();

    for (int i = 1; i <= n; i++)
        fill(lz[i], lz[i] + D, 1);

    int q;
    cin >> q;

    while (q--) {
        int t;
        cin >> t;

        if (t == 1) {
            int x, d, w;
            cin >> x >> d >> w;

            for (; d >= 0 && x > 0; d--, x = p[x])
                (lz[x][d] *= w) %= mod;
        }
        else {
            int x;
            cin >> x;

            ll ans = h[x];

            vector<int> a;
            int d = 0;
            for (; d < D - 1 && x > 0; d++, x = p[x])
                a.push_back(x);

            reverse(all(a));

            for (int v : a) {
                d--;
                if (v == a.front()) {
                    for (int i = d; i < D; i++)
                        (ans *= lz[v][i]) %= mod;
                }
                else
                    (ans *= lz[v][d] * lz[v][d + 1] % mod) %= mod;
            }

            cout << ans << '\n';
        }
    }

    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 3 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 3 ms 10076 KB Output is correct
6 Correct 3 ms 10064 KB Output is correct
7 Correct 3 ms 10076 KB Output is correct
8 Correct 3 ms 10076 KB Output is correct
9 Correct 3 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 8024 KB Output is correct
13 Correct 3 ms 8280 KB Output is correct
14 Correct 2 ms 8028 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 7772 KB Output is correct
17 Correct 3 ms 8028 KB Output is correct
18 Correct 3 ms 8024 KB Output is correct
19 Correct 2 ms 7772 KB Output is correct
20 Correct 2 ms 7772 KB Output is correct
21 Correct 2 ms 8028 KB Output is correct
22 Correct 2 ms 8024 KB Output is correct
23 Correct 2 ms 7768 KB Output is correct
24 Correct 2 ms 8024 KB Output is correct
25 Correct 2 ms 8004 KB Output is correct
26 Correct 2 ms 8024 KB Output is correct
27 Correct 3 ms 8028 KB Output is correct
28 Correct 2 ms 8024 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 643 ms 87904 KB Output is correct
3 Correct 268 ms 84548 KB Output is correct
4 Correct 527 ms 90148 KB Output is correct
5 Correct 440 ms 86220 KB Output is correct
6 Correct 308 ms 85972 KB Output is correct
7 Correct 295 ms 86552 KB Output is correct
8 Correct 223 ms 86880 KB Output is correct
9 Correct 791 ms 93580 KB Output is correct
10 Correct 299 ms 90232 KB Output is correct
11 Correct 589 ms 87684 KB Output is correct
12 Correct 275 ms 84564 KB Output is correct
13 Correct 177 ms 85112 KB Output is correct
14 Correct 181 ms 85124 KB Output is correct
15 Correct 194 ms 85292 KB Output is correct
16 Correct 175 ms 85172 KB Output is correct
17 Correct 189 ms 85788 KB Output is correct
18 Correct 2 ms 7796 KB Output is correct
19 Correct 2 ms 7772 KB Output is correct
20 Correct 2 ms 7772 KB Output is correct
21 Correct 2 ms 7772 KB Output is correct
22 Correct 2 ms 7772 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 643 ms 87904 KB Output is correct
3 Correct 268 ms 84548 KB Output is correct
4 Correct 527 ms 90148 KB Output is correct
5 Correct 440 ms 86220 KB Output is correct
6 Correct 308 ms 85972 KB Output is correct
7 Correct 295 ms 86552 KB Output is correct
8 Correct 223 ms 86880 KB Output is correct
9 Correct 791 ms 93580 KB Output is correct
10 Correct 299 ms 90232 KB Output is correct
11 Correct 589 ms 87684 KB Output is correct
12 Correct 275 ms 84564 KB Output is correct
13 Correct 177 ms 85112 KB Output is correct
14 Correct 181 ms 85124 KB Output is correct
15 Correct 194 ms 85292 KB Output is correct
16 Correct 175 ms 85172 KB Output is correct
17 Correct 189 ms 85788 KB Output is correct
18 Correct 2 ms 7796 KB Output is correct
19 Correct 2 ms 7772 KB Output is correct
20 Correct 2 ms 7772 KB Output is correct
21 Correct 2 ms 7772 KB Output is correct
22 Correct 2 ms 7772 KB Output is correct
23 Correct 2 ms 7772 KB Output is correct
24 Correct 641 ms 87780 KB Output is correct
25 Correct 291 ms 96540 KB Output is correct
26 Correct 579 ms 101912 KB Output is correct
27 Correct 488 ms 96220 KB Output is correct
28 Correct 307 ms 96336 KB Output is correct
29 Correct 284 ms 96080 KB Output is correct
30 Correct 254 ms 96964 KB Output is correct
31 Correct 859 ms 100084 KB Output is correct
32 Correct 312 ms 101804 KB Output is correct
33 Correct 577 ms 95988 KB Output is correct
34 Correct 288 ms 96464 KB Output is correct
35 Correct 2 ms 8024 KB Output is correct
36 Correct 2 ms 8024 KB Output is correct
37 Correct 2 ms 8028 KB Output is correct
38 Correct 2 ms 8028 KB Output is correct
39 Correct 2 ms 8020 KB Output is correct
40 Correct 2 ms 7768 KB Output is correct
41 Correct 2 ms 7768 KB Output is correct
42 Correct 2 ms 8016 KB Output is correct
43 Correct 2 ms 7772 KB Output is correct
44 Correct 3 ms 8024 KB Output is correct
45 Correct 2 ms 8028 KB Output is correct
46 Correct 2 ms 8012 KB Output is correct
47 Correct 2 ms 8028 KB Output is correct
48 Correct 2 ms 8028 KB Output is correct
49 Correct 2 ms 8280 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 845 ms 91240 KB Output is correct
3 Correct 566 ms 98264 KB Output is correct
4 Correct 609 ms 97920 KB Output is correct
5 Correct 536 ms 93164 KB Output is correct
6 Correct 329 ms 93520 KB Output is correct
7 Correct 295 ms 93484 KB Output is correct
8 Correct 244 ms 94016 KB Output is correct
9 Correct 859 ms 97084 KB Output is correct
10 Correct 561 ms 98944 KB Output is correct
11 Correct 651 ms 92984 KB Output is correct
12 Correct 388 ms 92500 KB Output is correct
13 Correct 268 ms 94604 KB Output is correct
14 Correct 256 ms 95056 KB Output is correct
15 Correct 2 ms 7772 KB Output is correct
16 Correct 3 ms 7772 KB Output is correct
17 Correct 2 ms 7772 KB Output is correct
18 Correct 2 ms 7772 KB Output is correct
19 Correct 2 ms 8028 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 862 ms 91828 KB Output is correct
3 Correct 538 ms 97108 KB Output is correct
4 Correct 597 ms 98140 KB Output is correct
5 Correct 520 ms 94876 KB Output is correct
6 Correct 333 ms 94932 KB Output is correct
7 Correct 315 ms 94748 KB Output is correct
8 Correct 242 ms 95000 KB Output is correct
9 Correct 871 ms 101532 KB Output is correct
10 Correct 495 ms 99664 KB Output is correct
11 Correct 629 ms 95532 KB Output is correct
12 Correct 425 ms 94156 KB Output is correct
13 Correct 272 ms 94860 KB Output is correct
14 Correct 284 ms 95508 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 2 ms 8028 KB Output is correct
19 Correct 2 ms 8024 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 3 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 3 ms 10076 KB Output is correct
6 Correct 3 ms 10064 KB Output is correct
7 Correct 3 ms 10076 KB Output is correct
8 Correct 3 ms 10076 KB Output is correct
9 Correct 3 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 8024 KB Output is correct
13 Correct 3 ms 8280 KB Output is correct
14 Correct 2 ms 8028 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 7772 KB Output is correct
17 Correct 3 ms 8028 KB Output is correct
18 Correct 3 ms 8024 KB Output is correct
19 Correct 2 ms 7772 KB Output is correct
20 Correct 2 ms 7772 KB Output is correct
21 Correct 2 ms 8028 KB Output is correct
22 Correct 2 ms 8024 KB Output is correct
23 Correct 2 ms 7768 KB Output is correct
24 Correct 2 ms 8024 KB Output is correct
25 Correct 2 ms 8004 KB Output is correct
26 Correct 2 ms 8024 KB Output is correct
27 Correct 3 ms 8028 KB Output is correct
28 Correct 2 ms 8024 KB Output is correct
29 Correct 2 ms 7768 KB Output is correct
30 Correct 643 ms 87904 KB Output is correct
31 Correct 268 ms 84548 KB Output is correct
32 Correct 527 ms 90148 KB Output is correct
33 Correct 440 ms 86220 KB Output is correct
34 Correct 308 ms 85972 KB Output is correct
35 Correct 295 ms 86552 KB Output is correct
36 Correct 223 ms 86880 KB Output is correct
37 Correct 791 ms 93580 KB Output is correct
38 Correct 299 ms 90232 KB Output is correct
39 Correct 589 ms 87684 KB Output is correct
40 Correct 275 ms 84564 KB Output is correct
41 Correct 177 ms 85112 KB Output is correct
42 Correct 181 ms 85124 KB Output is correct
43 Correct 194 ms 85292 KB Output is correct
44 Correct 175 ms 85172 KB Output is correct
45 Correct 189 ms 85788 KB Output is correct
46 Correct 2 ms 7796 KB Output is correct
47 Correct 2 ms 7772 KB Output is correct
48 Correct 2 ms 7772 KB Output is correct
49 Correct 2 ms 7772 KB Output is correct
50 Correct 2 ms 7772 KB Output is correct
51 Correct 2 ms 7772 KB Output is correct
52 Correct 641 ms 87780 KB Output is correct
53 Correct 291 ms 96540 KB Output is correct
54 Correct 579 ms 101912 KB Output is correct
55 Correct 488 ms 96220 KB Output is correct
56 Correct 307 ms 96336 KB Output is correct
57 Correct 284 ms 96080 KB Output is correct
58 Correct 254 ms 96964 KB Output is correct
59 Correct 859 ms 100084 KB Output is correct
60 Correct 312 ms 101804 KB Output is correct
61 Correct 577 ms 95988 KB Output is correct
62 Correct 288 ms 96464 KB Output is correct
63 Correct 2 ms 8024 KB Output is correct
64 Correct 2 ms 8024 KB Output is correct
65 Correct 2 ms 8028 KB Output is correct
66 Correct 2 ms 8028 KB Output is correct
67 Correct 2 ms 8020 KB Output is correct
68 Correct 2 ms 7768 KB Output is correct
69 Correct 2 ms 7768 KB Output is correct
70 Correct 2 ms 8016 KB Output is correct
71 Correct 2 ms 7772 KB Output is correct
72 Correct 3 ms 8024 KB Output is correct
73 Correct 2 ms 8028 KB Output is correct
74 Correct 2 ms 8012 KB Output is correct
75 Correct 2 ms 8028 KB Output is correct
76 Correct 2 ms 8028 KB Output is correct
77 Correct 2 ms 8280 KB Output is correct
78 Correct 2 ms 7772 KB Output is correct
79 Correct 845 ms 91240 KB Output is correct
80 Correct 566 ms 98264 KB Output is correct
81 Correct 609 ms 97920 KB Output is correct
82 Correct 536 ms 93164 KB Output is correct
83 Correct 329 ms 93520 KB Output is correct
84 Correct 295 ms 93484 KB Output is correct
85 Correct 244 ms 94016 KB Output is correct
86 Correct 859 ms 97084 KB Output is correct
87 Correct 561 ms 98944 KB Output is correct
88 Correct 651 ms 92984 KB Output is correct
89 Correct 388 ms 92500 KB Output is correct
90 Correct 268 ms 94604 KB Output is correct
91 Correct 256 ms 95056 KB Output is correct
92 Correct 2 ms 7772 KB Output is correct
93 Correct 3 ms 7772 KB Output is correct
94 Correct 2 ms 7772 KB Output is correct
95 Correct 2 ms 7772 KB Output is correct
96 Correct 2 ms 8028 KB Output is correct
97 Correct 2 ms 7772 KB Output is correct
98 Correct 862 ms 91828 KB Output is correct
99 Correct 538 ms 97108 KB Output is correct
100 Correct 597 ms 98140 KB Output is correct
101 Correct 520 ms 94876 KB Output is correct
102 Correct 333 ms 94932 KB Output is correct
103 Correct 315 ms 94748 KB Output is correct
104 Correct 242 ms 95000 KB Output is correct
105 Correct 871 ms 101532 KB Output is correct
106 Correct 495 ms 99664 KB Output is correct
107 Correct 629 ms 95532 KB Output is correct
108 Correct 425 ms 94156 KB Output is correct
109 Correct 272 ms 94860 KB Output is correct
110 Correct 284 ms 95508 KB Output is correct
111 Correct 2 ms 8028 KB Output is correct
112 Correct 2 ms 8028 KB Output is correct
113 Correct 2 ms 8028 KB Output is correct
114 Correct 2 ms 8028 KB Output is correct
115 Correct 2 ms 8024 KB Output is correct
116 Correct 700 ms 94032 KB Output is correct
117 Correct 389 ms 96600 KB Output is correct
118 Correct 615 ms 101792 KB Output is correct
119 Correct 538 ms 96172 KB Output is correct
120 Correct 339 ms 95824 KB Output is correct
121 Correct 351 ms 96612 KB Output is correct
122 Correct 276 ms 96968 KB Output is correct
123 Correct 866 ms 100968 KB Output is correct
124 Correct 534 ms 99872 KB Output is correct
125 Correct 706 ms 95056 KB Output is correct
126 Correct 478 ms 96500 KB Output is correct
127 Correct 431 ms 97112 KB Output is correct
128 Correct 323 ms 97616 KB Output is correct
129 Correct 334 ms 98192 KB Output is correct