oj.uz

Submission #874325

# Submission time Handle Problem Language Result Execution time Memory
874325 2023-11-16T16:42:40 Z svorogaze Sprinkler (JOI22_sprinkler) C++17
100 / 100
 606 ms 95520 KB 
/*
らららららららら らららららららら
らららららららら らららららららら
らららららららら らららららららら
らららららららら らららららららら
らららららららら らららららららら
らららららららら らららららららら
らららららららら らららららららら
らららららららら らららららららら
ハツネ祭り マジヤバイや
法事中も聴き涙 そりゃ病や
蟻食うバイトがあるけどまーいいや
京急の方の蒲田 満員や
ちょいNAMA-GUSAI シャングリラ
Jpopは だめだこりゃ
コス見りゃ婆 撮るのはマン
さあうたおー
Da-da-da-da-damn!
わけもなく
いみもなく
あめがふるように
Da-da-da-da-damn!
わけもなく
いみもなく
かぜがふくようにうたう
合成みたいなバランスの女装おじさん
学生に癖毛が生えたようなモーツァルト
母性溢れる鮟モチーフのマーメイド
音声祀りに集まった
ああ 最終学歴保育園でも
役3年目の米寿でも
年収図書券2～3枚でも
そこに行けば音はある
Da-da-da-da-damn!
わけもなく
いみもなく
あめがふるように
Da-da-da-da-damn!
わけもなく
いみもなく
かぜがふくように
Da-da-da-da-damn!
わけもなく
いみもなく
ただいきるように
Da-da-da-da-damn!
わけもなく
いみもなく
いきをするようにうたう
らららららららら らららららららら
らららららららら らららららららら
らららららららら らららららららら
らららららららら らららららららら
らららららららら らららららららら
らららららららら らららららららら
らららららららら らららららららら
らららららららら
*/

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, std::greater<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    indexed_set;
typedef tree<long long, null_type, greater_equal<>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define fastio \
    std::cin.tie(0), std::cout.tie(0), std::ios_base::sync_with_stdio(false)
#define rep(a, b, c, d) for (int a = b; a < c; a += d)
#define INF ((1ll << 48) - 1)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define x first
#define y second
#define ld long double
#define MAXN 201000
vector<vector<int>> g;
vector<int> p;
int de[200000];
int dp[200000][42];

void dfs1(int v, int pr) {
    p[v] = pr;
    if (pr == -1) de[v] = 0;
    else de[v] = de[pr] + 1;
    for (auto w : g[v]) {
        if (w != pr) dfs1(w, v);
    }
}

signed main() {
    fastio;
    for (auto& i : dp) for (auto& j : i) j = 1;
    int n, l;
    cin >> n >> l;
    g.resize(n);
    p.resize(n, -1);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> h(n);
    for (auto& i : h) cin >> i;
    dfs1(0, -1);
    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, d, w;
            cin >> x >> d >> w;
            x--;
            while (d >= 0) {
                if (x != 0) {
                    dp[x][d] = (dp[x][d] * w) % l;
                } else {
                    for (int j = 0; j <= d; j++) {
                        dp[x][j] = (dp[x][j] * w) % l;
                    }
                }
                d--;
                x = p[x];
                if (x == -1) break;
            }
        } else {
            int x;
            cin >> x;
            x--;
            int sx = x;
            int r = h[x];
            for (int i = 0; i <= 40 && x != 0; i++) {
                r = (r * dp[x][i]) % l;
                r = (r * dp[x][i + 1]) % l;
                x = p[x];
            }
            if (de[sx] <= 40) r = (r * dp[0][de[sx]]) % l;
            cout << r << '\n';
        }
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 66140 KB Output is correct
2 Correct 9 ms 66140 KB Output is correct
3 Correct 10 ms 66140 KB Output is correct
4 Correct 9 ms 66396 KB Output is correct
5 Correct 9 ms 66396 KB Output is correct
6 Correct 9 ms 66396 KB Output is correct
7 Correct 10 ms 66396 KB Output is correct
8 Correct 10 ms 66260 KB Output is correct
9 Correct 9 ms 66140 KB Output is correct
10 Correct 9 ms 66136 KB Output is correct
11 Correct 9 ms 66140 KB Output is correct
12 Correct 9 ms 66544 KB Output is correct
13 Correct 9 ms 66140 KB Output is correct
14 Correct 9 ms 66140 KB Output is correct
15 Correct 9 ms 66136 KB Output is correct
16 Correct 8 ms 66140 KB Output is correct
17 Correct 9 ms 66188 KB Output is correct
18 Correct 9 ms 66136 KB Output is correct
19 Correct 9 ms 66264 KB Output is correct
20 Correct 9 ms 66140 KB Output is correct
21 Correct 10 ms 66140 KB Output is correct
22 Correct 9 ms 66140 KB Output is correct
23 Correct 9 ms 66140 KB Output is correct
24 Correct 9 ms 66136 KB Output is correct
25 Correct 10 ms 66136 KB Output is correct
26 Correct 9 ms 66140 KB Output is correct
27 Correct 9 ms 66140 KB Output is correct
28 Correct 9 ms 66140 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 66560 KB Output is correct
2 Correct 493 ms 91132 KB Output is correct
3 Correct 283 ms 89680 KB Output is correct
4 Correct 419 ms 92916 KB Output is correct
5 Correct 372 ms 90500 KB Output is correct
6 Correct 260 ms 90052 KB Output is correct
7 Correct 269 ms 90840 KB Output is correct
8 Correct 209 ms 91000 KB Output is correct
9 Correct 603 ms 95520 KB Output is correct
10 Correct 286 ms 93780 KB Output is correct
11 Correct 449 ms 91276 KB Output is correct
12 Correct 276 ms 89632 KB Output is correct
13 Correct 189 ms 90052 KB Output is correct
14 Correct 191 ms 89860 KB Output is correct
15 Correct 190 ms 89860 KB Output is correct
16 Correct 192 ms 89948 KB Output is correct
17 Correct 194 ms 90464 KB Output is correct
18 Correct 9 ms 66396 KB Output is correct
19 Correct 10 ms 66140 KB Output is correct
20 Correct 9 ms 66140 KB Output is correct
21 Correct 8 ms 66140 KB Output is correct
22 Correct 9 ms 66480 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 66560 KB Output is correct
2 Correct 493 ms 91132 KB Output is correct
3 Correct 283 ms 89680 KB Output is correct
4 Correct 419 ms 92916 KB Output is correct
5 Correct 372 ms 90500 KB Output is correct
6 Correct 260 ms 90052 KB Output is correct
7 Correct 269 ms 90840 KB Output is correct
8 Correct 209 ms 91000 KB Output is correct
9 Correct 603 ms 95520 KB Output is correct
10 Correct 286 ms 93780 KB Output is correct
11 Correct 449 ms 91276 KB Output is correct
12 Correct 276 ms 89632 KB Output is correct
13 Correct 189 ms 90052 KB Output is correct
14 Correct 191 ms 89860 KB Output is correct
15 Correct 190 ms 89860 KB Output is correct
16 Correct 192 ms 89948 KB Output is correct
17 Correct 194 ms 90464 KB Output is correct
18 Correct 9 ms 66396 KB Output is correct
19 Correct 10 ms 66140 KB Output is correct
20 Correct 9 ms 66140 KB Output is correct
21 Correct 8 ms 66140 KB Output is correct
22 Correct 9 ms 66480 KB Output is correct
23 Correct 9 ms 66484 KB Output is correct
24 Correct 455 ms 91596 KB Output is correct
25 Correct 262 ms 89540 KB Output is correct
26 Correct 427 ms 95052 KB Output is correct
27 Correct 329 ms 90452 KB Output is correct
28 Correct 287 ms 90648 KB Output is correct
29 Correct 313 ms 90360 KB Output is correct
30 Correct 201 ms 90824 KB Output is correct
31 Correct 596 ms 94116 KB Output is correct
32 Correct 276 ms 93912 KB Output is correct
33 Correct 500 ms 91556 KB Output is correct
34 Correct 254 ms 89688 KB Output is correct
35 Correct 9 ms 66140 KB Output is correct
36 Correct 10 ms 66136 KB Output is correct
37 Correct 10 ms 66136 KB Output is correct
38 Correct 8 ms 66228 KB Output is correct
39 Correct 9 ms 66140 KB Output is correct
40 Correct 9 ms 66136 KB Output is correct
41 Correct 9 ms 66140 KB Output is correct
42 Correct 9 ms 66140 KB Output is correct
43 Correct 9 ms 66140 KB Output is correct
44 Correct 8 ms 66140 KB Output is correct
45 Correct 9 ms 66140 KB Output is correct
46 Correct 9 ms 66136 KB Output is correct
47 Correct 9 ms 66140 KB Output is correct
48 Correct 8 ms 66252 KB Output is correct
49 Correct 9 ms 66392 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 66296 KB Output is correct
2 Correct 571 ms 92996 KB Output is correct
3 Correct 533 ms 91360 KB Output is correct
4 Correct 475 ms 92188 KB Output is correct
5 Correct 369 ms 88160 KB Output is correct
6 Correct 277 ms 88572 KB Output is correct
7 Correct 289 ms 88308 KB Output is correct
8 Correct 198 ms 88908 KB Output is correct
9 Correct 560 ms 91204 KB Output is correct
10 Correct 520 ms 92756 KB Output is correct
11 Correct 436 ms 88012 KB Output is correct
12 Correct 424 ms 88164 KB Output is correct
13 Correct 282 ms 89168 KB Output is correct
14 Correct 289 ms 89972 KB Output is correct
15 Correct 9 ms 66140 KB Output is correct
16 Correct 9 ms 66292 KB Output is correct
17 Correct 10 ms 66140 KB Output is correct
18 Correct 9 ms 66228 KB Output is correct
19 Correct 9 ms 66136 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 66140 KB Output is correct
2 Correct 595 ms 93540 KB Output is correct
3 Correct 559 ms 90884 KB Output is correct
4 Correct 473 ms 91832 KB Output is correct
5 Correct 408 ms 89276 KB Output is correct
6 Correct 317 ms 89500 KB Output is correct
7 Correct 269 ms 89656 KB Output is correct
8 Correct 213 ms 90048 KB Output is correct
9 Correct 606 ms 94800 KB Output is correct
10 Correct 517 ms 92684 KB Output is correct
11 Correct 512 ms 90636 KB Output is correct
12 Correct 412 ms 88656 KB Output is correct
13 Correct 283 ms 89172 KB Output is correct
14 Correct 296 ms 90004 KB Output is correct
15 Correct 10 ms 66136 KB Output is correct
16 Correct 9 ms 66136 KB Output is correct
17 Correct 9 ms 66140 KB Output is correct
18 Correct 9 ms 66240 KB Output is correct
19 Correct 8 ms 66140 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 66140 KB Output is correct
2 Correct 9 ms 66140 KB Output is correct
3 Correct 10 ms 66140 KB Output is correct
4 Correct 9 ms 66396 KB Output is correct
5 Correct 9 ms 66396 KB Output is correct
6 Correct 9 ms 66396 KB Output is correct
7 Correct 10 ms 66396 KB Output is correct
8 Correct 10 ms 66260 KB Output is correct
9 Correct 9 ms 66140 KB Output is correct
10 Correct 9 ms 66136 KB Output is correct
11 Correct 9 ms 66140 KB Output is correct
12 Correct 9 ms 66544 KB Output is correct
13 Correct 9 ms 66140 KB Output is correct
14 Correct 9 ms 66140 KB Output is correct
15 Correct 9 ms 66136 KB Output is correct
16 Correct 8 ms 66140 KB Output is correct
17 Correct 9 ms 66188 KB Output is correct
18 Correct 9 ms 66136 KB Output is correct
19 Correct 9 ms 66264 KB Output is correct
20 Correct 9 ms 66140 KB Output is correct
21 Correct 10 ms 66140 KB Output is correct
22 Correct 9 ms 66140 KB Output is correct
23 Correct 9 ms 66140 KB Output is correct
24 Correct 9 ms 66136 KB Output is correct
25 Correct 10 ms 66136 KB Output is correct
26 Correct 9 ms 66140 KB Output is correct
27 Correct 9 ms 66140 KB Output is correct
28 Correct 9 ms 66140 KB Output is correct
29 Correct 8 ms 66560 KB Output is correct
30 Correct 493 ms 91132 KB Output is correct
31 Correct 283 ms 89680 KB Output is correct
32 Correct 419 ms 92916 KB Output is correct
33 Correct 372 ms 90500 KB Output is correct
34 Correct 260 ms 90052 KB Output is correct
35 Correct 269 ms 90840 KB Output is correct
36 Correct 209 ms 91000 KB Output is correct
37 Correct 603 ms 95520 KB Output is correct
38 Correct 286 ms 93780 KB Output is correct
39 Correct 449 ms 91276 KB Output is correct
40 Correct 276 ms 89632 KB Output is correct
41 Correct 189 ms 90052 KB Output is correct
42 Correct 191 ms 89860 KB Output is correct
43 Correct 190 ms 89860 KB Output is correct
44 Correct 192 ms 89948 KB Output is correct
45 Correct 194 ms 90464 KB Output is correct
46 Correct 9 ms 66396 KB Output is correct
47 Correct 10 ms 66140 KB Output is correct
48 Correct 9 ms 66140 KB Output is correct
49 Correct 8 ms 66140 KB Output is correct
50 Correct 9 ms 66480 KB Output is correct
51 Correct 9 ms 66484 KB Output is correct
52 Correct 455 ms 91596 KB Output is correct
53 Correct 262 ms 89540 KB Output is correct
54 Correct 427 ms 95052 KB Output is correct
55 Correct 329 ms 90452 KB Output is correct
56 Correct 287 ms 90648 KB Output is correct
57 Correct 313 ms 90360 KB Output is correct
58 Correct 201 ms 90824 KB Output is correct
59 Correct 596 ms 94116 KB Output is correct
60 Correct 276 ms 93912 KB Output is correct
61 Correct 500 ms 91556 KB Output is correct
62 Correct 254 ms 89688 KB Output is correct
63 Correct 9 ms 66140 KB Output is correct
64 Correct 10 ms 66136 KB Output is correct
65 Correct 10 ms 66136 KB Output is correct
66 Correct 8 ms 66228 KB Output is correct
67 Correct 9 ms 66140 KB Output is correct
68 Correct 9 ms 66136 KB Output is correct
69 Correct 9 ms 66140 KB Output is correct
70 Correct 9 ms 66140 KB Output is correct
71 Correct 9 ms 66140 KB Output is correct
72 Correct 8 ms 66140 KB Output is correct
73 Correct 9 ms 66140 KB Output is correct
74 Correct 9 ms 66136 KB Output is correct
75 Correct 9 ms 66140 KB Output is correct
76 Correct 8 ms 66252 KB Output is correct
77 Correct 9 ms 66392 KB Output is correct
78 Correct 10 ms 66296 KB Output is correct
79 Correct 571 ms 92996 KB Output is correct
80 Correct 533 ms 91360 KB Output is correct
81 Correct 475 ms 92188 KB Output is correct
82 Correct 369 ms 88160 KB Output is correct
83 Correct 277 ms 88572 KB Output is correct
84 Correct 289 ms 88308 KB Output is correct
85 Correct 198 ms 88908 KB Output is correct
86 Correct 560 ms 91204 KB Output is correct
87 Correct 520 ms 92756 KB Output is correct
88 Correct 436 ms 88012 KB Output is correct
89 Correct 424 ms 88164 KB Output is correct
90 Correct 282 ms 89168 KB Output is correct
91 Correct 289 ms 89972 KB Output is correct
92 Correct 9 ms 66140 KB Output is correct
93 Correct 9 ms 66292 KB Output is correct
94 Correct 10 ms 66140 KB Output is correct
95 Correct 9 ms 66228 KB Output is correct
96 Correct 9 ms 66136 KB Output is correct
97 Correct 9 ms 66140 KB Output is correct
98 Correct 595 ms 93540 KB Output is correct
99 Correct 559 ms 90884 KB Output is correct
100 Correct 473 ms 91832 KB Output is correct
101 Correct 408 ms 89276 KB Output is correct
102 Correct 317 ms 89500 KB Output is correct
103 Correct 269 ms 89656 KB Output is correct
104 Correct 213 ms 90048 KB Output is correct
105 Correct 606 ms 94800 KB Output is correct
106 Correct 517 ms 92684 KB Output is correct
107 Correct 512 ms 90636 KB Output is correct
108 Correct 412 ms 88656 KB Output is correct
109 Correct 283 ms 89172 KB Output is correct
110 Correct 296 ms 90004 KB Output is correct
111 Correct 10 ms 66136 KB Output is correct
112 Correct 9 ms 66136 KB Output is correct
113 Correct 9 ms 66140 KB Output is correct
114 Correct 9 ms 66240 KB Output is correct
115 Correct 8 ms 66140 KB Output is correct
116 Correct 463 ms 89016 KB Output is correct
117 Correct 453 ms 89172 KB Output is correct
118 Correct 489 ms 94496 KB Output is correct
119 Correct 416 ms 90208 KB Output is correct
120 Correct 305 ms 90196 KB Output is correct
121 Correct 302 ms 90404 KB Output is correct
122 Correct 217 ms 90628 KB Output is correct
123 Correct 556 ms 94548 KB Output is correct
124 Correct 547 ms 92068 KB Output is correct
125 Correct 450 ms 90228 KB Output is correct
126 Correct 446 ms 89516 KB Output is correct
127 Correct 438 ms 89684 KB Output is correct
128 Correct 348 ms 90428 KB Output is correct
129 Correct 329 ms 91440 KB Output is correct