oj.uz

Submission #614981

# Submission time Handle Problem Language Result Execution time Memory
614981 2022-07-31T05:57:54 Z 반딧불(#8492) Sprinkler (JOI22_sprinkler) C++17
9 / 100
 1054 ms 29372 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll MOD;

struct segTree{
    ll tree[800002], lazy[800002];

    void init(int i, int l, int r){
        tree[i] = 1, lazy[i] = 1;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
    }

    void propagate(int i, int l, int r){
        if(l==r) tree[i] = (tree[i] * lazy[i]) % MOD;
        if(l!=r) lazy[i*2] = (lazy[i*2] * lazy[i]) % MOD, lazy[i*2+1] = (lazy[i*2+1] * lazy[i]) % MOD;
        lazy[i] = 1;
    }

    void update(int i, int l, int r, int s, int e, ll v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] = v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);
    }

    ll query(int i, int l, int r, int x){
        propagate(i, l, r);
        if(l==r) return tree[i];
        int m = (l+r)>>1;
        if(x<=m) return query(i*2, l, m, x);
        else return query(i*2+1, m+1, r, x);
    }
} tree;

int n, q;
vector<int> link[200002];
ll arr[200002];
int in[200002], childL[200002], childR[200002], idx[200002], par[200002], depth[200002], inCnt;

void bfs(int x){
    queue<int> que;
    que.push(1);
    while(!que.empty()){
        int x = que.front(); que.pop();
        in[x] = ++inCnt;
        idx[inCnt] = x;
        if(!childL[par[x]]) childL[par[x]] = inCnt;
        childR[par[x]] = inCnt;
        for(auto y: link[x]){
            if(in[y]) continue;
            par[y] = x;
            depth[y] = depth[x] + 1;
            link[y].erase(find(link[y].begin(), link[y].end(), x));
            que.push(y);
        }
    }
}

int main(){
    scanf("%d %lld", &n, &MOD);
    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        link[y].push_back(x);
    }
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
    bfs(1);
    tree.init(1, 1, n);
    for(int i=1; i<=n; i++) tree.update(1, 1, n, in[i], in[i], arr[i]);

    scanf("%d", &q);
    while(q--){
        int qt;
        scanf("%d", &qt);
        if(qt==1){
            int x, d; ll w;
            scanf("%d %d %lld", &x, &d, &w);
            tree.update(1, 1, n, in[x], in[x], w);
            if(d){
                if(childR[x]) tree.update(1, 1, n, childL[x], childR[x], w);
                if(par[x]) tree.update(1, 1, n, in[par[x]], in[par[x]], w);
            }
        }
        else{
            int x;
            scanf("%d", &x);
            printf("%lld\n", tree.query(1, 1, n, in[x]));
        }
    }
}

Compilation message

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d %lld", &n, &MOD);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
sprinkler.cpp:79:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~
sprinkler.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
sprinkler.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         scanf("%d", &qt);
      |         ~~~~~^~~~~~~~~~~
sprinkler.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |             scanf("%d %d %lld", &x, &d, &w);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:99:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 546 ms 29256 KB Output is correct
3 Correct 940 ms 26124 KB Output is correct
4 Correct 737 ms 27588 KB Output is correct
5 Correct 687 ms 27772 KB Output is correct
6 Correct 595 ms 27796 KB Output is correct
7 Correct 630 ms 28168 KB Output is correct
8 Correct 577 ms 27672 KB Output is correct
9 Correct 572 ms 29060 KB Output is correct
10 Correct 927 ms 26120 KB Output is correct
11 Correct 566 ms 29304 KB Output is correct
12 Correct 980 ms 26180 KB Output is correct
13 Correct 1054 ms 27512 KB Output is correct
14 Correct 981 ms 27152 KB Output is correct
15 Correct 922 ms 27096 KB Output is correct
16 Correct 916 ms 26936 KB Output is correct
17 Correct 885 ms 27464 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 4 ms 5064 KB Output is correct
20 Correct 3 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
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 546 ms 29256 KB Output is correct
3 Correct 940 ms 26124 KB Output is correct
4 Correct 737 ms 27588 KB Output is correct
5 Correct 687 ms 27772 KB Output is correct
6 Correct 595 ms 27796 KB Output is correct
7 Correct 630 ms 28168 KB Output is correct
8 Correct 577 ms 27672 KB Output is correct
9 Correct 572 ms 29060 KB Output is correct
10 Correct 927 ms 26120 KB Output is correct
11 Correct 566 ms 29304 KB Output is correct
12 Correct 980 ms 26180 KB Output is correct
13 Correct 1054 ms 27512 KB Output is correct
14 Correct 981 ms 27152 KB Output is correct
15 Correct 922 ms 27096 KB Output is correct
16 Correct 916 ms 26936 KB Output is correct
17 Correct 885 ms 27464 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 4 ms 5064 KB Output is correct
20 Correct 3 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 3 ms 4948 KB Output is correct
24 Incorrect 558 ms 29372 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 573 ms 28496 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -