oj.uz

Submission #874326

# Submission time Handle Problem Language Result Execution time Memory
874326 2023-11-16T16:46:03 Z svorogaze Sprinkler (JOI22_sprinkler) C++17
100 / 100
 610 ms 91152 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 && x != 0) {
                dp[x][d] = (dp[x][d] * w) % l;
                d--;
                x = p[x];
            }
            if (d >= 0) {
                for (int j = 0; j <= d; ++j) {
                    dp[x][j] = (dp[x][j] * w) % l;
                }
            }
        } 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 66240 KB Output is correct
3 Correct 9 ms 66140 KB Output is correct
4 Correct 9 ms 66184 KB Output is correct
5 Correct 9 ms 66140 KB Output is correct
6 Correct 9 ms 66140 KB Output is correct
7 Correct 9 ms 66140 KB Output is correct
8 Correct 9 ms 66140 KB Output is correct
9 Correct 9 ms 66140 KB Output is correct
10 Correct 9 ms 66140 KB Output is correct
11 Correct 8 ms 66140 KB Output is correct
12 Correct 10 ms 66216 KB Output is correct
13 Correct 8 ms 66140 KB Output is correct
14 Correct 9 ms 66204 KB Output is correct
15 Correct 9 ms 66140 KB Output is correct
16 Correct 9 ms 66140 KB Output is correct
17 Correct 9 ms 66164 KB Output is correct
18 Correct 10 ms 66140 KB Output is correct
19 Correct 10 ms 66396 KB Output is correct
20 Correct 8 ms 66140 KB Output is correct
21 Correct 8 ms 66140 KB Output is correct
22 Correct 8 ms 66140 KB Output is correct
23 Correct 8 ms 66136 KB Output is correct
24 Correct 9 ms 66140 KB Output is correct
25 Correct 8 ms 66140 KB Output is correct
26 Correct 9 ms 66136 KB Output is correct
27 Correct 9 ms 66140 KB Output is correct
28 Correct 9 ms 66204 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 66140 KB Output is correct
2 Correct 435 ms 86472 KB Output is correct
3 Correct 286 ms 83284 KB Output is correct
4 Correct 464 ms 87464 KB Output is correct
5 Correct 353 ms 84976 KB Output is correct
6 Correct 260 ms 84816 KB Output is correct
7 Correct 243 ms 85076 KB Output is correct
8 Correct 197 ms 85184 KB Output is correct
9 Correct 536 ms 91152 KB Output is correct
10 Correct 266 ms 87376 KB Output is correct
11 Correct 436 ms 87028 KB Output is correct
12 Correct 253 ms 83208 KB Output is correct
13 Correct 166 ms 83452 KB Output is correct
14 Correct 167 ms 83536 KB Output is correct
15 Correct 167 ms 83384 KB Output is correct
16 Correct 174 ms 83380 KB Output is correct
17 Correct 185 ms 84540 KB Output is correct
18 Correct 9 ms 66140 KB Output is correct
19 Correct 9 ms 66260 KB Output is correct
20 Correct 10 ms 66140 KB Output is correct
21 Correct 9 ms 66184 KB Output is correct
22 Correct 9 ms 66140 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 66140 KB Output is correct
2 Correct 435 ms 86472 KB Output is correct
3 Correct 286 ms 83284 KB Output is correct
4 Correct 464 ms 87464 KB Output is correct
5 Correct 353 ms 84976 KB Output is correct
6 Correct 260 ms 84816 KB Output is correct
7 Correct 243 ms 85076 KB Output is correct
8 Correct 197 ms 85184 KB Output is correct
9 Correct 536 ms 91152 KB Output is correct
10 Correct 266 ms 87376 KB Output is correct
11 Correct 436 ms 87028 KB Output is correct
12 Correct 253 ms 83208 KB Output is correct
13 Correct 166 ms 83452 KB Output is correct
14 Correct 167 ms 83536 KB Output is correct
15 Correct 167 ms 83384 KB Output is correct
16 Correct 174 ms 83380 KB Output is correct
17 Correct 185 ms 84540 KB Output is correct
18 Correct 9 ms 66140 KB Output is correct
19 Correct 9 ms 66260 KB Output is correct
20 Correct 10 ms 66140 KB Output is correct
21 Correct 9 ms 66184 KB Output is correct
22 Correct 9 ms 66140 KB Output is correct
23 Correct 8 ms 66136 KB Output is correct
24 Correct 436 ms 86672 KB Output is correct
25 Correct 256 ms 83128 KB Output is correct
26 Correct 424 ms 89420 KB Output is correct
27 Correct 336 ms 84780 KB Output is correct
28 Correct 269 ms 85116 KB Output is correct
29 Correct 257 ms 84976 KB Output is correct
30 Correct 194 ms 85188 KB Output is correct
31 Correct 531 ms 89172 KB Output is correct
32 Correct 289 ms 87644 KB Output is correct
33 Correct 417 ms 86372 KB Output is correct
34 Correct 306 ms 83232 KB Output is correct
35 Correct 9 ms 66140 KB Output is correct
36 Correct 8 ms 66224 KB Output is correct
37 Correct 9 ms 66140 KB Output is correct
38 Correct 9 ms 66300 KB Output is correct
39 Correct 9 ms 66140 KB Output is correct
40 Correct 9 ms 66140 KB Output is correct
41 Correct 8 ms 66136 KB Output is correct
42 Correct 8 ms 66140 KB Output is correct
43 Correct 9 ms 66140 KB Output is correct
44 Correct 10 ms 66136 KB Output is correct
45 Correct 11 ms 66140 KB Output is correct
46 Correct 9 ms 66188 KB Output is correct
47 Correct 9 ms 66140 KB Output is correct
48 Correct 9 ms 66244 KB Output is correct
49 Correct 9 ms 66140 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 66136 KB Output is correct
2 Correct 567 ms 88532 KB Output is correct
3 Correct 490 ms 86208 KB Output is correct
4 Correct 474 ms 86912 KB Output is correct
5 Correct 389 ms 83280 KB Output is correct
6 Correct 278 ms 83284 KB Output is correct
7 Correct 247 ms 83600 KB Output is correct
8 Correct 193 ms 83720 KB Output is correct
9 Correct 585 ms 86992 KB Output is correct
10 Correct 529 ms 87128 KB Output is correct
11 Correct 436 ms 83816 KB Output is correct
12 Correct 408 ms 82768 KB Output is correct
13 Correct 276 ms 83916 KB Output is correct
14 Correct 287 ms 84656 KB Output is correct
15 Correct 9 ms 66140 KB Output is correct
16 Correct 9 ms 66232 KB Output is correct
17 Correct 9 ms 66140 KB Output is correct
18 Correct 9 ms 66140 KB Output is correct
19 Correct 8 ms 66140 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 66136 KB Output is correct
2 Correct 610 ms 89136 KB Output is correct
3 Correct 526 ms 85344 KB Output is correct
4 Correct 477 ms 87300 KB Output is correct
5 Correct 389 ms 84684 KB Output is correct
6 Correct 301 ms 85164 KB Output is correct
7 Correct 265 ms 84816 KB Output is correct
8 Correct 206 ms 85444 KB Output is correct
9 Correct 556 ms 90448 KB Output is correct
10 Correct 522 ms 87632 KB Output is correct
11 Correct 480 ms 86612 KB Output is correct
12 Correct 409 ms 83176 KB Output is correct
13 Correct 283 ms 84080 KB Output is correct
14 Correct 287 ms 84744 KB Output is correct
15 Correct 9 ms 66140 KB Output is correct
16 Correct 9 ms 66244 KB Output is correct
17 Correct 9 ms 66220 KB Output is correct
18 Correct 8 ms 66220 KB Output is correct
19 Correct 8 ms 66136 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 66240 KB Output is correct
3 Correct 9 ms 66140 KB Output is correct
4 Correct 9 ms 66184 KB Output is correct
5 Correct 9 ms 66140 KB Output is correct
6 Correct 9 ms 66140 KB Output is correct
7 Correct 9 ms 66140 KB Output is correct
8 Correct 9 ms 66140 KB Output is correct
9 Correct 9 ms 66140 KB Output is correct
10 Correct 9 ms 66140 KB Output is correct
11 Correct 8 ms 66140 KB Output is correct
12 Correct 10 ms 66216 KB Output is correct
13 Correct 8 ms 66140 KB Output is correct
14 Correct 9 ms 66204 KB Output is correct
15 Correct 9 ms 66140 KB Output is correct
16 Correct 9 ms 66140 KB Output is correct
17 Correct 9 ms 66164 KB Output is correct
18 Correct 10 ms 66140 KB Output is correct
19 Correct 10 ms 66396 KB Output is correct
20 Correct 8 ms 66140 KB Output is correct
21 Correct 8 ms 66140 KB Output is correct
22 Correct 8 ms 66140 KB Output is correct
23 Correct 8 ms 66136 KB Output is correct
24 Correct 9 ms 66140 KB Output is correct
25 Correct 8 ms 66140 KB Output is correct
26 Correct 9 ms 66136 KB Output is correct
27 Correct 9 ms 66140 KB Output is correct
28 Correct 9 ms 66204 KB Output is correct
29 Correct 8 ms 66140 KB Output is correct
30 Correct 435 ms 86472 KB Output is correct
31 Correct 286 ms 83284 KB Output is correct
32 Correct 464 ms 87464 KB Output is correct
33 Correct 353 ms 84976 KB Output is correct
34 Correct 260 ms 84816 KB Output is correct
35 Correct 243 ms 85076 KB Output is correct
36 Correct 197 ms 85184 KB Output is correct
37 Correct 536 ms 91152 KB Output is correct
38 Correct 266 ms 87376 KB Output is correct
39 Correct 436 ms 87028 KB Output is correct
40 Correct 253 ms 83208 KB Output is correct
41 Correct 166 ms 83452 KB Output is correct
42 Correct 167 ms 83536 KB Output is correct
43 Correct 167 ms 83384 KB Output is correct
44 Correct 174 ms 83380 KB Output is correct
45 Correct 185 ms 84540 KB Output is correct
46 Correct 9 ms 66140 KB Output is correct
47 Correct 9 ms 66260 KB Output is correct
48 Correct 10 ms 66140 KB Output is correct
49 Correct 9 ms 66184 KB Output is correct
50 Correct 9 ms 66140 KB Output is correct
51 Correct 8 ms 66136 KB Output is correct
52 Correct 436 ms 86672 KB Output is correct
53 Correct 256 ms 83128 KB Output is correct
54 Correct 424 ms 89420 KB Output is correct
55 Correct 336 ms 84780 KB Output is correct
56 Correct 269 ms 85116 KB Output is correct
57 Correct 257 ms 84976 KB Output is correct
58 Correct 194 ms 85188 KB Output is correct
59 Correct 531 ms 89172 KB Output is correct
60 Correct 289 ms 87644 KB Output is correct
61 Correct 417 ms 86372 KB Output is correct
62 Correct 306 ms 83232 KB Output is correct
63 Correct 9 ms 66140 KB Output is correct
64 Correct 8 ms 66224 KB Output is correct
65 Correct 9 ms 66140 KB Output is correct
66 Correct 9 ms 66300 KB Output is correct
67 Correct 9 ms 66140 KB Output is correct
68 Correct 9 ms 66140 KB Output is correct
69 Correct 8 ms 66136 KB Output is correct
70 Correct 8 ms 66140 KB Output is correct
71 Correct 9 ms 66140 KB Output is correct
72 Correct 10 ms 66136 KB Output is correct
73 Correct 11 ms 66140 KB Output is correct
74 Correct 9 ms 66188 KB Output is correct
75 Correct 9 ms 66140 KB Output is correct
76 Correct 9 ms 66244 KB Output is correct
77 Correct 9 ms 66140 KB Output is correct
78 Correct 10 ms 66136 KB Output is correct
79 Correct 567 ms 88532 KB Output is correct
80 Correct 490 ms 86208 KB Output is correct
81 Correct 474 ms 86912 KB Output is correct
82 Correct 389 ms 83280 KB Output is correct
83 Correct 278 ms 83284 KB Output is correct
84 Correct 247 ms 83600 KB Output is correct
85 Correct 193 ms 83720 KB Output is correct
86 Correct 585 ms 86992 KB Output is correct
87 Correct 529 ms 87128 KB Output is correct
88 Correct 436 ms 83816 KB Output is correct
89 Correct 408 ms 82768 KB Output is correct
90 Correct 276 ms 83916 KB Output is correct
91 Correct 287 ms 84656 KB Output is correct
92 Correct 9 ms 66140 KB Output is correct
93 Correct 9 ms 66232 KB Output is correct
94 Correct 9 ms 66140 KB Output is correct
95 Correct 9 ms 66140 KB Output is correct
96 Correct 8 ms 66140 KB Output is correct
97 Correct 8 ms 66136 KB Output is correct
98 Correct 610 ms 89136 KB Output is correct
99 Correct 526 ms 85344 KB Output is correct
100 Correct 477 ms 87300 KB Output is correct
101 Correct 389 ms 84684 KB Output is correct
102 Correct 301 ms 85164 KB Output is correct
103 Correct 265 ms 84816 KB Output is correct
104 Correct 206 ms 85444 KB Output is correct
105 Correct 556 ms 90448 KB Output is correct
106 Correct 522 ms 87632 KB Output is correct
107 Correct 480 ms 86612 KB Output is correct
108 Correct 409 ms 83176 KB Output is correct
109 Correct 283 ms 84080 KB Output is correct
110 Correct 287 ms 84744 KB Output is correct
111 Correct 9 ms 66140 KB Output is correct
112 Correct 9 ms 66244 KB Output is correct
113 Correct 9 ms 66220 KB Output is correct
114 Correct 8 ms 66220 KB Output is correct
115 Correct 8 ms 66136 KB Output is correct
116 Correct 451 ms 84396 KB Output is correct
117 Correct 431 ms 83112 KB Output is correct
118 Correct 555 ms 89264 KB Output is correct
119 Correct 413 ms 84820 KB Output is correct
120 Correct 309 ms 84704 KB Output is correct
121 Correct 304 ms 85076 KB Output is correct
122 Correct 213 ms 85188 KB Output is correct
123 Correct 579 ms 89724 KB Output is correct
124 Correct 548 ms 85496 KB Output is correct
125 Correct 453 ms 85728 KB Output is correct
126 Correct 440 ms 83088 KB Output is correct
127 Correct 442 ms 83284 KB Output is correct
128 Correct 320 ms 83800 KB Output is correct
129 Correct 331 ms 84820 KB Output is correct