oj.uz

Submission #614983

# Submission time Handle Problem Language Result Execution time Memory
614983 2022-07-31T05:58:30 Z 박상훈(#8491) Sprinkler (JOI22_sprinkler) C++17
100 / 100
 2951 ms 128464 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int MOD;
int n, a[200200];
vector<int> adj[200200];
int L[200200][41], R[200200][41], par[200200][41], INV[200200], f[200200], b[200200], mx[200200];

struct Seg{
    ll tree[400400], sz;
    void init(int n){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = a[INV[i-sz]];
        for (int i=sz-1;i;i--) tree[i] = 1;
    }
    void update(int l, int r, int x){
        ++r;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1){
                tree[l] = tree[l] * x % MOD;
                l++;
            }
            if (r&1){
                --r;
                tree[r] = tree[r] * x % MOD;
            }
        }
    }
    ll query(int x){
        ll ret = 1;
        x += sz;
        for (;x;x>>=1) ret = ret * tree[x] % MOD;
        return ret;
    }
}tree;




void bfs(){
    int cnt = 0;
    queue<int> q;
    fill(par[1]+1, par[1]+41, -1);
    par[1][0] = 1;
    mx[1] = 0;
    q.push(1);

    while(!q.empty()){
        int s = q.front(); q.pop();
        L[s][0] = ++cnt;
        R[s][0] = cnt;
        INV[cnt] = s;

        f[s] = -1, b[s] = -1;

        for (auto &v:adj[s]) if (v!=par[s][1]){
            b[s] = v;
            if (f[s]==-1) f[s] = v;

            q.push(v);
            par[v][0] = v;
            for (int i=1;i<=40;i++) par[v][i] = par[s][i-1];
            mx[v] = min(mx[s]+1, 40);
        }
    }

    for (int i=n;i;i--){
        int s = INV[i];

        fill(L[s]+1, L[s]+41, 1e9);
        fill(R[s]+1, R[s]+41, -1e9);

        for (auto &v:adj[s]) if (v!=par[s][1]){
            for (int j=1;j<=40;j++){
                L[s][j] = min(L[s][j], L[v][j-1]);
                R[s][j] = max(R[s][j], R[v][j-1]);
            }
        }
    }
}

void update(int s, int d, int w){
    for (int i=0;i<=d;i++){ ///dep -> i higher
        int k = (d-i) / 2;
        int up = min(mx[s], i+k);
        if (up<i) continue;

        int l = L[par[s][up]][up-i], r = R[par[s][up]][up-i];
        tree.update(l, r, w);
    }

    for (int i=1;i<=d;i++){ ///dep -> i lower
        int k = (d-i) / 2;
        int up = min(mx[s], k);

        int l = L[par[s][up]][up+i], r = R[par[s][up]][up+i];
        if (l==1e9) return;
        tree.update(l, r, w);
    }
}

ll query(int s){
    return tree.query(L[s][0]);
}

int main(){
    scanf("%d %d", &n, &MOD);
    for (int i=1;i<=n-1;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    bfs();

    for (int i=1;i<=n;i++) scanf("%d", a+i);
    tree.init(n+1);

    int q;
    scanf("%d", &q);
    while(q--){
        int op;
        scanf("%d", &op);
        if (op==1){
            int x, d, k;
            scanf("%d %d %d", &x, &d, &k);
            update(x, d, k);
        }
        else{
            int x;
            scanf("%d", &x);
            printf("%lld\n", query(x));
        }
    }
    return 0;
}

Compilation message

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d %d", &n, &MOD);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
sprinkler.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
sprinkler.cpp:118:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |     for (int i=1;i<=n;i++) scanf("%d", a+i);
      |                            ~~~~~^~~~~~~~~~~
sprinkler.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
sprinkler.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         scanf("%d", &op);
      |         ~~~~~^~~~~~~~~~~
sprinkler.cpp:128:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |             scanf("%d %d %d", &x, &d, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:133:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 5588 KB Output is correct
5 Correct 5 ms 5588 KB Output is correct
6 Correct 5 ms 5588 KB Output is correct
7 Correct 5 ms 5588 KB Output is correct
8 Correct 5 ms 5588 KB Output is correct
9 Correct 3 ms 5008 KB Output is correct
10 Correct 4 ms 5020 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5028 KB Output is correct
15 Correct 4 ms 5024 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 4 ms 5020 KB Output is correct
18 Correct 5 ms 5076 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 4 ms 4948 KB Output is correct
21 Correct 4 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 5016 KB Output is correct
24 Correct 4 ms 4948 KB Output is correct
25 Correct 3 ms 5020 KB Output is correct
26 Correct 3 ms 5076 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 3 ms 5076 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 650 ms 118132 KB Output is correct
3 Correct 703 ms 115124 KB Output is correct
4 Correct 674 ms 116508 KB Output is correct
5 Correct 653 ms 116532 KB Output is correct
6 Correct 689 ms 116788 KB Output is correct
7 Correct 686 ms 117052 KB Output is correct
8 Correct 553 ms 118136 KB Output is correct
9 Correct 589 ms 117924 KB Output is correct
10 Correct 695 ms 115020 KB Output is correct
11 Correct 632 ms 118104 KB Output is correct
12 Correct 757 ms 115148 KB Output is correct
13 Correct 543 ms 116348 KB Output is correct
14 Correct 552 ms 116008 KB Output is correct
15 Correct 525 ms 115848 KB Output is correct
16 Correct 534 ms 116096 KB Output is correct
17 Correct 630 ms 116312 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 4 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 650 ms 118132 KB Output is correct
3 Correct 703 ms 115124 KB Output is correct
4 Correct 674 ms 116508 KB Output is correct
5 Correct 653 ms 116532 KB Output is correct
6 Correct 689 ms 116788 KB Output is correct
7 Correct 686 ms 117052 KB Output is correct
8 Correct 553 ms 118136 KB Output is correct
9 Correct 589 ms 117924 KB Output is correct
10 Correct 695 ms 115020 KB Output is correct
11 Correct 632 ms 118104 KB Output is correct
12 Correct 757 ms 115148 KB Output is correct
13 Correct 543 ms 116348 KB Output is correct
14 Correct 552 ms 116008 KB Output is correct
15 Correct 525 ms 115848 KB Output is correct
16 Correct 534 ms 116096 KB Output is correct
17 Correct 630 ms 116312 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 4 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 4 ms 4948 KB Output is correct
24 Correct 676 ms 118140 KB Output is correct
25 Correct 762 ms 126924 KB Output is correct
26 Correct 666 ms 126516 KB Output is correct
27 Correct 668 ms 126508 KB Output is correct
28 Correct 685 ms 126880 KB Output is correct
29 Correct 694 ms 126784 KB Output is correct
30 Correct 663 ms 128368 KB Output is correct
31 Correct 651 ms 126376 KB Output is correct
32 Correct 764 ms 126796 KB Output is correct
33 Correct 609 ms 126412 KB Output is correct
34 Correct 717 ms 126924 KB Output is correct
35 Correct 3 ms 5076 KB Output is correct
36 Correct 3 ms 5076 KB Output is correct
37 Correct 4 ms 5076 KB Output is correct
38 Correct 4 ms 5076 KB Output is correct
39 Correct 3 ms 5028 KB Output is correct
40 Correct 3 ms 4948 KB Output is correct
41 Correct 3 ms 5048 KB Output is correct
42 Correct 3 ms 4948 KB Output is correct
43 Correct 3 ms 4948 KB Output is correct
44 Correct 3 ms 4948 KB Output is correct
45 Correct 3 ms 5016 KB Output is correct
46 Correct 3 ms 5020 KB Output is correct
47 Correct 3 ms 5020 KB Output is correct
48 Correct 3 ms 5020 KB Output is correct
49 Correct 3 ms 5076 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 796 ms 115368 KB Output is correct
3 Correct 2410 ms 114768 KB Output is correct
4 Correct 1109 ms 115096 KB Output is correct
5 Correct 1154 ms 114972 KB Output is correct
6 Correct 855 ms 124036 KB Output is correct
7 Correct 777 ms 124168 KB Output is correct
8 Correct 565 ms 125264 KB Output is correct
9 Correct 817 ms 123360 KB Output is correct
10 Correct 2392 ms 123988 KB Output is correct
11 Correct 875 ms 123256 KB Output is correct
12 Correct 2489 ms 124180 KB Output is correct
13 Correct 2736 ms 125208 KB Output is correct
14 Correct 2686 ms 125732 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 3 ms 5016 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 822 ms 118196 KB Output is correct
3 Correct 2428 ms 114984 KB Output is correct
4 Correct 1145 ms 116496 KB Output is correct
5 Correct 1190 ms 116724 KB Output is correct
6 Correct 986 ms 125580 KB Output is correct
7 Correct 800 ms 125332 KB Output is correct
8 Correct 551 ms 126440 KB Output is correct
9 Correct 819 ms 125984 KB Output is correct
10 Correct 2313 ms 124544 KB Output is correct
11 Correct 820 ms 126124 KB Output is correct
12 Correct 2501 ms 124672 KB Output is correct
13 Correct 2771 ms 125520 KB Output is correct
14 Correct 2808 ms 125736 KB Output is correct
15 Correct 4 ms 5076 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 5588 KB Output is correct
5 Correct 5 ms 5588 KB Output is correct
6 Correct 5 ms 5588 KB Output is correct
7 Correct 5 ms 5588 KB Output is correct
8 Correct 5 ms 5588 KB Output is correct
9 Correct 3 ms 5008 KB Output is correct
10 Correct 4 ms 5020 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5028 KB Output is correct
15 Correct 4 ms 5024 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 4 ms 5020 KB Output is correct
18 Correct 5 ms 5076 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 4 ms 4948 KB Output is correct
21 Correct 4 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 5016 KB Output is correct
24 Correct 4 ms 4948 KB Output is correct
25 Correct 3 ms 5020 KB Output is correct
26 Correct 3 ms 5076 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 3 ms 5076 KB Output is correct
29 Correct 3 ms 4948 KB Output is correct
30 Correct 650 ms 118132 KB Output is correct
31 Correct 703 ms 115124 KB Output is correct
32 Correct 674 ms 116508 KB Output is correct
33 Correct 653 ms 116532 KB Output is correct
34 Correct 689 ms 116788 KB Output is correct
35 Correct 686 ms 117052 KB Output is correct
36 Correct 553 ms 118136 KB Output is correct
37 Correct 589 ms 117924 KB Output is correct
38 Correct 695 ms 115020 KB Output is correct
39 Correct 632 ms 118104 KB Output is correct
40 Correct 757 ms 115148 KB Output is correct
41 Correct 543 ms 116348 KB Output is correct
42 Correct 552 ms 116008 KB Output is correct
43 Correct 525 ms 115848 KB Output is correct
44 Correct 534 ms 116096 KB Output is correct
45 Correct 630 ms 116312 KB Output is correct
46 Correct 3 ms 4948 KB Output is correct
47 Correct 3 ms 4948 KB Output is correct
48 Correct 4 ms 4948 KB Output is correct
49 Correct 3 ms 4948 KB Output is correct
50 Correct 3 ms 4948 KB Output is correct
51 Correct 4 ms 4948 KB Output is correct
52 Correct 676 ms 118140 KB Output is correct
53 Correct 762 ms 126924 KB Output is correct
54 Correct 666 ms 126516 KB Output is correct
55 Correct 668 ms 126508 KB Output is correct
56 Correct 685 ms 126880 KB Output is correct
57 Correct 694 ms 126784 KB Output is correct
58 Correct 663 ms 128368 KB Output is correct
59 Correct 651 ms 126376 KB Output is correct
60 Correct 764 ms 126796 KB Output is correct
61 Correct 609 ms 126412 KB Output is correct
62 Correct 717 ms 126924 KB Output is correct
63 Correct 3 ms 5076 KB Output is correct
64 Correct 3 ms 5076 KB Output is correct
65 Correct 4 ms 5076 KB Output is correct
66 Correct 4 ms 5076 KB Output is correct
67 Correct 3 ms 5028 KB Output is correct
68 Correct 3 ms 4948 KB Output is correct
69 Correct 3 ms 5048 KB Output is correct
70 Correct 3 ms 4948 KB Output is correct
71 Correct 3 ms 4948 KB Output is correct
72 Correct 3 ms 4948 KB Output is correct
73 Correct 3 ms 5016 KB Output is correct
74 Correct 3 ms 5020 KB Output is correct
75 Correct 3 ms 5020 KB Output is correct
76 Correct 3 ms 5020 KB Output is correct
77 Correct 3 ms 5076 KB Output is correct
78 Correct 3 ms 4948 KB Output is correct
79 Correct 796 ms 115368 KB Output is correct
80 Correct 2410 ms 114768 KB Output is correct
81 Correct 1109 ms 115096 KB Output is correct
82 Correct 1154 ms 114972 KB Output is correct
83 Correct 855 ms 124036 KB Output is correct
84 Correct 777 ms 124168 KB Output is correct
85 Correct 565 ms 125264 KB Output is correct
86 Correct 817 ms 123360 KB Output is correct
87 Correct 2392 ms 123988 KB Output is correct
88 Correct 875 ms 123256 KB Output is correct
89 Correct 2489 ms 124180 KB Output is correct
90 Correct 2736 ms 125208 KB Output is correct
91 Correct 2686 ms 125732 KB Output is correct
92 Correct 3 ms 4948 KB Output is correct
93 Correct 4 ms 4948 KB Output is correct
94 Correct 3 ms 5016 KB Output is correct
95 Correct 3 ms 4948 KB Output is correct
96 Correct 3 ms 5076 KB Output is correct
97 Correct 3 ms 4948 KB Output is correct
98 Correct 822 ms 118196 KB Output is correct
99 Correct 2428 ms 114984 KB Output is correct
100 Correct 1145 ms 116496 KB Output is correct
101 Correct 1190 ms 116724 KB Output is correct
102 Correct 986 ms 125580 KB Output is correct
103 Correct 800 ms 125332 KB Output is correct
104 Correct 551 ms 126440 KB Output is correct
105 Correct 819 ms 125984 KB Output is correct
106 Correct 2313 ms 124544 KB Output is correct
107 Correct 820 ms 126124 KB Output is correct
108 Correct 2501 ms 124672 KB Output is correct
109 Correct 2771 ms 125520 KB Output is correct
110 Correct 2808 ms 125736 KB Output is correct
111 Correct 4 ms 5076 KB Output is correct
112 Correct 3 ms 5076 KB Output is correct
113 Correct 3 ms 4948 KB Output is correct
114 Correct 3 ms 5076 KB Output is correct
115 Correct 3 ms 5076 KB Output is correct
116 Correct 771 ms 124436 KB Output is correct
117 Correct 2518 ms 126956 KB Output is correct
118 Correct 1211 ms 126580 KB Output is correct
119 Correct 1342 ms 126720 KB Output is correct
120 Correct 1244 ms 126560 KB Output is correct
121 Correct 1052 ms 127184 KB Output is correct
122 Correct 545 ms 128288 KB Output is correct
123 Correct 883 ms 126332 KB Output is correct
124 Correct 2477 ms 126512 KB Output is correct
125 Correct 871 ms 125536 KB Output is correct
126 Correct 2560 ms 126828 KB Output is correct
127 Correct 2790 ms 127348 KB Output is correct
128 Correct 2951 ms 128008 KB Output is correct
129 Correct 2886 ms 128464 KB Output is correct