oj.uz

Submission #614975

# Submission time Handle Problem Language Result Execution time Memory
614975 2022-07-31T05:51:54 Z 박상훈(#8491) Sprinkler (JOI22_sprinkler) C++17
9 / 100
 2370 ms 128164 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];
        if (f[s]==-1){
            fill(L[s]+1, L[s]+41, -1);
            fill(R[s]+1, R[s]+41, -1);
            continue;
        }

        for (int j=1;j<=40;j++){
            L[s][j] = L[f[s]][j-1];
            R[s][j] = R[b[s]][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==-1) 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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 4 ms 5544 KB Output is correct
5 Incorrect 5 ms 5540 KB Output isn't correct
6 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 588 ms 121948 KB Output is correct
3 Correct 661 ms 118572 KB Output is correct
4 Correct 577 ms 119896 KB Output is correct
5 Correct 598 ms 120112 KB Output is correct
6 Correct 569 ms 120148 KB Output is correct
7 Correct 594 ms 120552 KB Output is correct
8 Correct 517 ms 121760 KB Output is correct
9 Correct 570 ms 121764 KB Output is correct
10 Correct 610 ms 118356 KB Output is correct
11 Correct 503 ms 121852 KB Output is correct
12 Correct 658 ms 118560 KB Output is correct
13 Correct 478 ms 127284 KB Output is correct
14 Correct 489 ms 128060 KB Output is correct
15 Correct 430 ms 127220 KB Output is correct
16 Correct 450 ms 127848 KB Output is correct
17 Correct 454 ms 128164 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5024 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 5076 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 588 ms 121948 KB Output is correct
3 Correct 661 ms 118572 KB Output is correct
4 Correct 577 ms 119896 KB Output is correct
5 Correct 598 ms 120112 KB Output is correct
6 Correct 569 ms 120148 KB Output is correct
7 Correct 594 ms 120552 KB Output is correct
8 Correct 517 ms 121760 KB Output is correct
9 Correct 570 ms 121764 KB Output is correct
10 Correct 610 ms 118356 KB Output is correct
11 Correct 503 ms 121852 KB Output is correct
12 Correct 658 ms 118560 KB Output is correct
13 Correct 478 ms 127284 KB Output is correct
14 Correct 489 ms 128060 KB Output is correct
15 Correct 430 ms 127220 KB Output is correct
16 Correct 450 ms 127848 KB Output is correct
17 Correct 454 ms 128164 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5024 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct
23 Correct 3 ms 5016 KB Output is correct
24 Incorrect 545 ms 126488 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 5012 KB Output is correct
2 Correct 734 ms 119312 KB Output is correct
3 Correct 2370 ms 118328 KB Output is correct
4 Correct 1044 ms 123568 KB Output is correct
5 Incorrect 776 ms 123668 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 773 ms 121796 KB Output is correct
3 Correct 2277 ms 118628 KB Output is correct
4 Correct 1040 ms 125088 KB Output is correct
5 Incorrect 873 ms 125336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 4 ms 5544 KB Output is correct
5 Incorrect 5 ms 5540 KB Output isn't correct
6 Halted 0 ms 0 KB -