oj.uz

Submission #874324

# Submission time Handle Problem Language Result Execution time Memory
874324 2023-11-16T16:37:45 Z svorogaze Sprinkler (JOI22_sprinkler) C++17
100 / 100
 670 ms 93328 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 dp[200000][42];

void dfs1(int v, int pr) {
    p[v] = pr;
    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;
                    }
                    break;
                }
                d--;
                x = p[x];
            }
        } else {
            int x;
            cin >> x;
            x--;
            int r = h[x];
            for (int i = 0; i <= 40; i++) {
                if (x != 0) {
                    r = (r * dp[x][i]) % l;
                    r = (r * dp[x][i + 1]) % l;
                } else {
                    r = (r * dp[x][i]) % l;
                    break;
                }
                x = p[x];
            }
            cout << r << '\n';
        }
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 66140 KB Output is correct
2 Correct 9 ms 66136 KB Output is correct
3 Correct 9 ms 66140 KB Output is correct
4 Correct 10 ms 66140 KB Output is correct
5 Correct 10 ms 66136 KB Output is correct
6 Correct 9 ms 66140 KB Output is correct
7 Correct 10 ms 66232 KB Output is correct
8 Correct 10 ms 66184 KB Output is correct
9 Correct 9 ms 66000 KB Output is correct
10 Correct 9 ms 66140 KB Output is correct
11 Correct 9 ms 66140 KB Output is correct
12 Correct 10 ms 66140 KB Output is correct
13 Correct 9 ms 66140 KB Output is correct
14 Correct 9 ms 66140 KB Output is correct
15 Correct 11 ms 66476 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 66224 KB Output is correct
19 Correct 9 ms 66140 KB Output is correct
20 Correct 9 ms 66140 KB Output is correct
21 Correct 9 ms 66024 KB Output is correct
22 Correct 9 ms 66140 KB Output is correct
23 Correct 10 ms 65984 KB Output is correct
24 Correct 9 ms 66208 KB Output is correct
25 Correct 9 ms 66140 KB Output is correct
26 Correct 9 ms 66136 KB Output is correct
27 Correct 9 ms 65984 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 9 ms 66140 KB Output is correct
2 Correct 421 ms 89424 KB Output is correct
3 Correct 264 ms 88408 KB Output is correct
4 Correct 412 ms 91036 KB Output is correct
5 Correct 383 ms 88768 KB Output is correct
6 Correct 249 ms 88520 KB Output is correct
7 Correct 284 ms 89100 KB Output is correct
8 Correct 207 ms 89128 KB Output is correct
9 Correct 549 ms 93328 KB Output is correct
10 Correct 292 ms 91820 KB Output is correct
11 Correct 425 ms 89424 KB Output is correct
12 Correct 259 ms 88156 KB Output is correct
13 Correct 165 ms 88340 KB Output is correct
14 Correct 169 ms 88504 KB Output is correct
15 Correct 182 ms 87988 KB Output is correct
16 Correct 173 ms 88268 KB Output is correct
17 Correct 197 ms 88880 KB Output is correct
18 Correct 9 ms 66140 KB Output is correct
19 Correct 9 ms 66140 KB Output is correct
20 Correct 9 ms 66140 KB Output is correct
21 Correct 9 ms 66140 KB Output is correct
22 Correct 10 ms 66140 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 66140 KB Output is correct
2 Correct 421 ms 89424 KB Output is correct
3 Correct 264 ms 88408 KB Output is correct
4 Correct 412 ms 91036 KB Output is correct
5 Correct 383 ms 88768 KB Output is correct
6 Correct 249 ms 88520 KB Output is correct
7 Correct 284 ms 89100 KB Output is correct
8 Correct 207 ms 89128 KB Output is correct
9 Correct 549 ms 93328 KB Output is correct
10 Correct 292 ms 91820 KB Output is correct
11 Correct 425 ms 89424 KB Output is correct
12 Correct 259 ms 88156 KB Output is correct
13 Correct 165 ms 88340 KB Output is correct
14 Correct 169 ms 88504 KB Output is correct
15 Correct 182 ms 87988 KB Output is correct
16 Correct 173 ms 88268 KB Output is correct
17 Correct 197 ms 88880 KB Output is correct
18 Correct 9 ms 66140 KB Output is correct
19 Correct 9 ms 66140 KB Output is correct
20 Correct 9 ms 66140 KB Output is correct
21 Correct 9 ms 66140 KB Output is correct
22 Correct 10 ms 66140 KB Output is correct
23 Correct 9 ms 66204 KB Output is correct
24 Correct 446 ms 89276 KB Output is correct
25 Correct 289 ms 88448 KB Output is correct
26 Correct 408 ms 92756 KB Output is correct
27 Correct 351 ms 88644 KB Output is correct
28 Correct 268 ms 88696 KB Output is correct
29 Correct 272 ms 88708 KB Output is correct
30 Correct 196 ms 89028 KB Output is correct
31 Correct 568 ms 92096 KB Output is correct
32 Correct 279 ms 91988 KB Output is correct
33 Correct 439 ms 89504 KB Output is correct
34 Correct 256 ms 88144 KB Output is correct
35 Correct 9 ms 66140 KB Output is correct
36 Correct 9 ms 65984 KB Output is correct
37 Correct 10 ms 66216 KB Output is correct
38 Correct 9 ms 66140 KB Output is correct
39 Correct 9 ms 66140 KB Output is correct
40 Correct 10 ms 66180 KB Output is correct
41 Correct 9 ms 66136 KB Output is correct
42 Correct 9 ms 66140 KB Output is correct
43 Correct 9 ms 66136 KB Output is correct
44 Correct 9 ms 66136 KB Output is correct
45 Correct 9 ms 66136 KB Output is correct
46 Correct 9 ms 66140 KB Output is correct
47 Correct 9 ms 66140 KB Output is correct
48 Correct 9 ms 66028 KB Output is correct
49 Correct 11 ms 66140 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 66212 KB Output is correct
2 Correct 556 ms 90668 KB Output is correct
3 Correct 512 ms 89736 KB Output is correct
4 Correct 461 ms 90204 KB Output is correct
5 Correct 396 ms 86568 KB Output is correct
6 Correct 276 ms 86908 KB Output is correct
7 Correct 273 ms 86860 KB Output is correct
8 Correct 190 ms 86924 KB Output is correct
9 Correct 557 ms 89268 KB Output is correct
10 Correct 516 ms 85500 KB Output is correct
11 Correct 438 ms 82004 KB Output is correct
12 Correct 429 ms 81372 KB Output is correct
13 Correct 297 ms 82452 KB Output is correct
14 Correct 274 ms 83096 KB Output is correct
15 Correct 9 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 65968 KB Output is correct
19 Correct 9 ms 66380 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 65996 KB Output is correct
2 Correct 670 ms 87404 KB Output is correct
3 Correct 559 ms 83544 KB Output is correct
4 Correct 488 ms 85332 KB Output is correct
5 Correct 380 ms 83288 KB Output is correct
6 Correct 293 ms 83264 KB Output is correct
7 Correct 267 ms 83292 KB Output is correct
8 Correct 200 ms 83460 KB Output is correct
9 Correct 589 ms 88660 KB Output is correct
10 Correct 509 ms 85828 KB Output is correct
11 Correct 458 ms 84720 KB Output is correct
12 Correct 404 ms 81648 KB Output is correct
13 Correct 281 ms 82256 KB Output is correct
14 Correct 287 ms 83260 KB Output is correct
15 Correct 9 ms 66136 KB Output is correct
16 Correct 9 ms 66140 KB Output is correct
17 Correct 9 ms 66212 KB Output is correct
18 Correct 9 ms 66000 KB Output is correct
19 Correct 9 ms 66204 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 66140 KB Output is correct
2 Correct 9 ms 66136 KB Output is correct
3 Correct 9 ms 66140 KB Output is correct
4 Correct 10 ms 66140 KB Output is correct
5 Correct 10 ms 66136 KB Output is correct
6 Correct 9 ms 66140 KB Output is correct
7 Correct 10 ms 66232 KB Output is correct
8 Correct 10 ms 66184 KB Output is correct
9 Correct 9 ms 66000 KB Output is correct
10 Correct 9 ms 66140 KB Output is correct
11 Correct 9 ms 66140 KB Output is correct
12 Correct 10 ms 66140 KB Output is correct
13 Correct 9 ms 66140 KB Output is correct
14 Correct 9 ms 66140 KB Output is correct
15 Correct 11 ms 66476 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 66224 KB Output is correct
19 Correct 9 ms 66140 KB Output is correct
20 Correct 9 ms 66140 KB Output is correct
21 Correct 9 ms 66024 KB Output is correct
22 Correct 9 ms 66140 KB Output is correct
23 Correct 10 ms 65984 KB Output is correct
24 Correct 9 ms 66208 KB Output is correct
25 Correct 9 ms 66140 KB Output is correct
26 Correct 9 ms 66136 KB Output is correct
27 Correct 9 ms 65984 KB Output is correct
28 Correct 9 ms 66140 KB Output is correct
29 Correct 9 ms 66140 KB Output is correct
30 Correct 421 ms 89424 KB Output is correct
31 Correct 264 ms 88408 KB Output is correct
32 Correct 412 ms 91036 KB Output is correct
33 Correct 383 ms 88768 KB Output is correct
34 Correct 249 ms 88520 KB Output is correct
35 Correct 284 ms 89100 KB Output is correct
36 Correct 207 ms 89128 KB Output is correct
37 Correct 549 ms 93328 KB Output is correct
38 Correct 292 ms 91820 KB Output is correct
39 Correct 425 ms 89424 KB Output is correct
40 Correct 259 ms 88156 KB Output is correct
41 Correct 165 ms 88340 KB Output is correct
42 Correct 169 ms 88504 KB Output is correct
43 Correct 182 ms 87988 KB Output is correct
44 Correct 173 ms 88268 KB Output is correct
45 Correct 197 ms 88880 KB Output is correct
46 Correct 9 ms 66140 KB Output is correct
47 Correct 9 ms 66140 KB Output is correct
48 Correct 9 ms 66140 KB Output is correct
49 Correct 9 ms 66140 KB Output is correct
50 Correct 10 ms 66140 KB Output is correct
51 Correct 9 ms 66204 KB Output is correct
52 Correct 446 ms 89276 KB Output is correct
53 Correct 289 ms 88448 KB Output is correct
54 Correct 408 ms 92756 KB Output is correct
55 Correct 351 ms 88644 KB Output is correct
56 Correct 268 ms 88696 KB Output is correct
57 Correct 272 ms 88708 KB Output is correct
58 Correct 196 ms 89028 KB Output is correct
59 Correct 568 ms 92096 KB Output is correct
60 Correct 279 ms 91988 KB Output is correct
61 Correct 439 ms 89504 KB Output is correct
62 Correct 256 ms 88144 KB Output is correct
63 Correct 9 ms 66140 KB Output is correct
64 Correct 9 ms 65984 KB Output is correct
65 Correct 10 ms 66216 KB Output is correct
66 Correct 9 ms 66140 KB Output is correct
67 Correct 9 ms 66140 KB Output is correct
68 Correct 10 ms 66180 KB Output is correct
69 Correct 9 ms 66136 KB Output is correct
70 Correct 9 ms 66140 KB Output is correct
71 Correct 9 ms 66136 KB Output is correct
72 Correct 9 ms 66136 KB Output is correct
73 Correct 9 ms 66136 KB Output is correct
74 Correct 9 ms 66140 KB Output is correct
75 Correct 9 ms 66140 KB Output is correct
76 Correct 9 ms 66028 KB Output is correct
77 Correct 11 ms 66140 KB Output is correct
78 Correct 9 ms 66212 KB Output is correct
79 Correct 556 ms 90668 KB Output is correct
80 Correct 512 ms 89736 KB Output is correct
81 Correct 461 ms 90204 KB Output is correct
82 Correct 396 ms 86568 KB Output is correct
83 Correct 276 ms 86908 KB Output is correct
84 Correct 273 ms 86860 KB Output is correct
85 Correct 190 ms 86924 KB Output is correct
86 Correct 557 ms 89268 KB Output is correct
87 Correct 516 ms 85500 KB Output is correct
88 Correct 438 ms 82004 KB Output is correct
89 Correct 429 ms 81372 KB Output is correct
90 Correct 297 ms 82452 KB Output is correct
91 Correct 274 ms 83096 KB Output is correct
92 Correct 9 ms 66136 KB Output is correct
93 Correct 9 ms 66136 KB Output is correct
94 Correct 9 ms 66140 KB Output is correct
95 Correct 9 ms 65968 KB Output is correct
96 Correct 9 ms 66380 KB Output is correct
97 Correct 9 ms 65996 KB Output is correct
98 Correct 670 ms 87404 KB Output is correct
99 Correct 559 ms 83544 KB Output is correct
100 Correct 488 ms 85332 KB Output is correct
101 Correct 380 ms 83288 KB Output is correct
102 Correct 293 ms 83264 KB Output is correct
103 Correct 267 ms 83292 KB Output is correct
104 Correct 200 ms 83460 KB Output is correct
105 Correct 589 ms 88660 KB Output is correct
106 Correct 509 ms 85828 KB Output is correct
107 Correct 458 ms 84720 KB Output is correct
108 Correct 404 ms 81648 KB Output is correct
109 Correct 281 ms 82256 KB Output is correct
110 Correct 287 ms 83260 KB Output is correct
111 Correct 9 ms 66136 KB Output is correct
112 Correct 9 ms 66140 KB Output is correct
113 Correct 9 ms 66212 KB Output is correct
114 Correct 9 ms 66000 KB Output is correct
115 Correct 9 ms 66204 KB Output is correct
116 Correct 448 ms 83064 KB Output is correct
117 Correct 453 ms 81424 KB Output is correct
118 Correct 483 ms 87148 KB Output is correct
119 Correct 425 ms 83392 KB Output is correct
120 Correct 297 ms 83028 KB Output is correct
121 Correct 302 ms 84032 KB Output is correct
122 Correct 232 ms 83652 KB Output is correct
123 Correct 587 ms 88232 KB Output is correct
124 Correct 548 ms 84188 KB Output is correct
125 Correct 451 ms 84304 KB Output is correct
126 Correct 466 ms 81424 KB Output is correct
127 Correct 433 ms 81488 KB Output is correct
128 Correct 323 ms 82268 KB Output is correct
129 Correct 335 ms 83036 KB Output is correct