oj.uz

Submission #615344

# Submission time Handle Problem Language Result Execution time Memory
615344 2022-07-31T08:30:10 Z 반딧불(#8492) Sprinkler (JOI22_sprinkler) C++17
41 / 100
 4000 ms 890392 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
ll MOD;

struct Query{
    int l, r; ll v;
    Query(){}
    Query(int l, int r, ll v): l(l), r(r), v(v){}
};

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);
    }

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

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

    inline 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], idx[200002], par[200002], depth[200002], inCnt;
int childL[200002][42], childR[200002][42];

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;
        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);
        }
    }
}

void dfs(int x, int p=-1){
    childL[x][0] = childR[x][0] = in[x];
    for(auto y: link[x]){
        dfs(y);
        for(int i=1; i<=40; i++){
            childL[x][i] = min(childL[x][i], childL[y][i-1]);
            childR[x][i] = max(childR[x][i], childR[y][i-1]);
        }
    }
}

int treeL[82], treeR[82];
vector<Query> queryVec[200002];

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]);
    for(int i=1; i<=n; i++){
        for(int j=0; j<=40; j++){
            childL[i][j] = 1e9;
            childR[i][j] = -1;
        }
    }
    dfs(1);

    scanf("%d", &q);
    while(q--){
        int qt;
        scanf("%d", &qt);
        if(qt==1){
            int x, d, dp; ll w;
            scanf("%d %d %lld", &x, &d, &w);
            dp=depth[x];
            for(int i=0; i<=d+d; i++) treeL[i] = 1e9, treeR[i] = -1;
            int up = 0;
            for(up=0; up<=d; up++){
                /// ������ �ִ� ����: d-up-up
                treeL[d+d-up-up] = min(treeL[d+d-up-up], childL[x][d-up]);
                treeR[d+d-up-up] = max(treeR[d+d-up-up], childR[x][d-up]);
                if(up==d) break;
                /// ������ �ִ� ����: d-up-up-1
                treeL[d+d-up-up-1] = min(treeL[d+d-up-up-1], childL[x][d-up-1]);
                treeR[d+d-up-up-1] = max(treeR[d+d-up-up-1], childR[x][d-up-1]);

                if(!par[x]) break;
                x = par[x];
            }
            for(int cnt=0; cnt+up<=d; cnt++){
                treeL[d-up+cnt] = min(treeL[d-up+cnt], childL[x][cnt]);
                treeR[d-up+cnt] = max(treeR[d-up+cnt], childR[x][cnt]);
            }

            for(int i=0; i<=d+d; i++){
                if(treeL[i] == 1e9) continue;
                queryVec[dp-d+i].push_back(Query(treeL[i], treeR[i], w));
            }
        }
        else{
            int x;
            scanf("%d", &x);
            while(!queryVec[depth[x]].empty()){
                Query tmp = queryVec[depth[x]].back();
                queryVec[depth[x]].pop_back();
                tree.update(1, 1, n, tmp.l, tmp.r, tmp.v);
            }
            printf("%lld\n", tree.query(1, 1, n, in[x]));
        }
    }
}

Compilation message

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9764 KB Output is correct
4 Correct 8 ms 10580 KB Output is correct
5 Correct 9 ms 10324 KB Output is correct
6 Correct 11 ms 10196 KB Output is correct
7 Correct 9 ms 10176 KB Output is correct
8 Correct 8 ms 10196 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 7 ms 9684 KB Output is correct
12 Correct 5 ms 9656 KB Output is correct
13 Correct 6 ms 9684 KB Output is correct
14 Correct 6 ms 9684 KB Output is correct
15 Correct 6 ms 9684 KB Output is correct
16 Correct 7 ms 9732 KB Output is correct
17 Correct 7 ms 9684 KB Output is correct
18 Correct 6 ms 9684 KB Output is correct
19 Correct 5 ms 9812 KB Output is correct
20 Correct 9 ms 9640 KB Output is correct
21 Correct 6 ms 9764 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 5 ms 9684 KB Output is correct
24 Correct 6 ms 9684 KB Output is correct
25 Correct 6 ms 9684 KB Output is correct
26 Correct 6 ms 9680 KB Output is correct
27 Correct 7 ms 9684 KB Output is correct
28 Correct 6 ms 9684 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 602 ms 98432 KB Output is correct
3 Correct 823 ms 97540 KB Output is correct
4 Correct 667 ms 114704 KB Output is correct
5 Correct 640 ms 97060 KB Output is correct
6 Correct 556 ms 96644 KB Output is correct
7 Correct 595 ms 97136 KB Output is correct
8 Correct 521 ms 99048 KB Output is correct
9 Correct 561 ms 116376 KB Output is correct
10 Correct 699 ms 135100 KB Output is correct
11 Correct 466 ms 98432 KB Output is correct
12 Correct 699 ms 97872 KB Output is correct
13 Correct 586 ms 108736 KB Output is correct
14 Correct 599 ms 103060 KB Output is correct
15 Correct 575 ms 98360 KB Output is correct
16 Correct 559 ms 97080 KB Output is correct
17 Correct 606 ms 96732 KB Output is correct
18 Correct 6 ms 9684 KB Output is correct
19 Correct 6 ms 9684 KB Output is correct
20 Correct 5 ms 9684 KB Output is correct
21 Correct 6 ms 9680 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 602 ms 98432 KB Output is correct
3 Correct 823 ms 97540 KB Output is correct
4 Correct 667 ms 114704 KB Output is correct
5 Correct 640 ms 97060 KB Output is correct
6 Correct 556 ms 96644 KB Output is correct
7 Correct 595 ms 97136 KB Output is correct
8 Correct 521 ms 99048 KB Output is correct
9 Correct 561 ms 116376 KB Output is correct
10 Correct 699 ms 135100 KB Output is correct
11 Correct 466 ms 98432 KB Output is correct
12 Correct 699 ms 97872 KB Output is correct
13 Correct 586 ms 108736 KB Output is correct
14 Correct 599 ms 103060 KB Output is correct
15 Correct 575 ms 98360 KB Output is correct
16 Correct 559 ms 97080 KB Output is correct
17 Correct 606 ms 96732 KB Output is correct
18 Correct 6 ms 9684 KB Output is correct
19 Correct 6 ms 9684 KB Output is correct
20 Correct 5 ms 9684 KB Output is correct
21 Correct 6 ms 9680 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 7 ms 9648 KB Output is correct
24 Correct 637 ms 98448 KB Output is correct
25 Correct 896 ms 99056 KB Output is correct
26 Correct 838 ms 124232 KB Output is correct
27 Correct 790 ms 97204 KB Output is correct
28 Correct 768 ms 96780 KB Output is correct
29 Correct 746 ms 96920 KB Output is correct
30 Correct 583 ms 101140 KB Output is correct
31 Correct 651 ms 112872 KB Output is correct
32 Correct 854 ms 152904 KB Output is correct
33 Correct 534 ms 98444 KB Output is correct
34 Correct 871 ms 98572 KB Output is correct
35 Correct 5 ms 9684 KB Output is correct
36 Correct 5 ms 9684 KB Output is correct
37 Correct 5 ms 9668 KB Output is correct
38 Correct 6 ms 9684 KB Output is correct
39 Correct 6 ms 9684 KB Output is correct
40 Correct 5 ms 9684 KB Output is correct
41 Correct 5 ms 9636 KB Output is correct
42 Correct 5 ms 9684 KB Output is correct
43 Correct 5 ms 9684 KB Output is correct
44 Correct 5 ms 9684 KB Output is correct
45 Correct 5 ms 9684 KB Output is correct
46 Correct 5 ms 9684 KB Output is correct
47 Correct 5 ms 9684 KB Output is correct
48 Correct 6 ms 9684 KB Output is correct
49 Correct 6 ms 9684 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9732 KB Output is correct
2 Correct 1252 ms 166116 KB Output is correct
3 Correct 3092 ms 853664 KB Output is correct
4 Correct 2003 ms 262844 KB Output is correct
5 Correct 2214 ms 99208 KB Output is correct
6 Correct 1891 ms 100004 KB Output is correct
7 Correct 1449 ms 104852 KB Output is correct
8 Correct 528 ms 103600 KB Output is correct
9 Correct 1229 ms 154332 KB Output is correct
10 Correct 3430 ms 886316 KB Output is correct
11 Correct 1262 ms 96884 KB Output is correct
12 Execution timed out 4065 ms 161828 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 1248 ms 154692 KB Output is correct
3 Correct 3138 ms 868960 KB Output is correct
4 Correct 1530 ms 249940 KB Output is correct
5 Correct 1994 ms 102480 KB Output is correct
6 Correct 1768 ms 105380 KB Output is correct
7 Correct 1409 ms 104832 KB Output is correct
8 Correct 553 ms 103740 KB Output is correct
9 Correct 1162 ms 167144 KB Output is correct
10 Correct 2933 ms 890392 KB Output is correct
11 Correct 1220 ms 99612 KB Output is correct
12 Execution timed out 4080 ms 136880 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9764 KB Output is correct
4 Correct 8 ms 10580 KB Output is correct
5 Correct 9 ms 10324 KB Output is correct
6 Correct 11 ms 10196 KB Output is correct
7 Correct 9 ms 10176 KB Output is correct
8 Correct 8 ms 10196 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 7 ms 9684 KB Output is correct
12 Correct 5 ms 9656 KB Output is correct
13 Correct 6 ms 9684 KB Output is correct
14 Correct 6 ms 9684 KB Output is correct
15 Correct 6 ms 9684 KB Output is correct
16 Correct 7 ms 9732 KB Output is correct
17 Correct 7 ms 9684 KB Output is correct
18 Correct 6 ms 9684 KB Output is correct
19 Correct 5 ms 9812 KB Output is correct
20 Correct 9 ms 9640 KB Output is correct
21 Correct 6 ms 9764 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 5 ms 9684 KB Output is correct
24 Correct 6 ms 9684 KB Output is correct
25 Correct 6 ms 9684 KB Output is correct
26 Correct 6 ms 9680 KB Output is correct
27 Correct 7 ms 9684 KB Output is correct
28 Correct 6 ms 9684 KB Output is correct
29 Correct 5 ms 9684 KB Output is correct
30 Correct 602 ms 98432 KB Output is correct
31 Correct 823 ms 97540 KB Output is correct
32 Correct 667 ms 114704 KB Output is correct
33 Correct 640 ms 97060 KB Output is correct
34 Correct 556 ms 96644 KB Output is correct
35 Correct 595 ms 97136 KB Output is correct
36 Correct 521 ms 99048 KB Output is correct
37 Correct 561 ms 116376 KB Output is correct
38 Correct 699 ms 135100 KB Output is correct
39 Correct 466 ms 98432 KB Output is correct
40 Correct 699 ms 97872 KB Output is correct
41 Correct 586 ms 108736 KB Output is correct
42 Correct 599 ms 103060 KB Output is correct
43 Correct 575 ms 98360 KB Output is correct
44 Correct 559 ms 97080 KB Output is correct
45 Correct 606 ms 96732 KB Output is correct
46 Correct 6 ms 9684 KB Output is correct
47 Correct 6 ms 9684 KB Output is correct
48 Correct 5 ms 9684 KB Output is correct
49 Correct 6 ms 9680 KB Output is correct
50 Correct 6 ms 9684 KB Output is correct
51 Correct 7 ms 9648 KB Output is correct
52 Correct 637 ms 98448 KB Output is correct
53 Correct 896 ms 99056 KB Output is correct
54 Correct 838 ms 124232 KB Output is correct
55 Correct 790 ms 97204 KB Output is correct
56 Correct 768 ms 96780 KB Output is correct
57 Correct 746 ms 96920 KB Output is correct
58 Correct 583 ms 101140 KB Output is correct
59 Correct 651 ms 112872 KB Output is correct
60 Correct 854 ms 152904 KB Output is correct
61 Correct 534 ms 98444 KB Output is correct
62 Correct 871 ms 98572 KB Output is correct
63 Correct 5 ms 9684 KB Output is correct
64 Correct 5 ms 9684 KB Output is correct
65 Correct 5 ms 9668 KB Output is correct
66 Correct 6 ms 9684 KB Output is correct
67 Correct 6 ms 9684 KB Output is correct
68 Correct 5 ms 9684 KB Output is correct
69 Correct 5 ms 9636 KB Output is correct
70 Correct 5 ms 9684 KB Output is correct
71 Correct 5 ms 9684 KB Output is correct
72 Correct 5 ms 9684 KB Output is correct
73 Correct 5 ms 9684 KB Output is correct
74 Correct 5 ms 9684 KB Output is correct
75 Correct 5 ms 9684 KB Output is correct
76 Correct 6 ms 9684 KB Output is correct
77 Correct 6 ms 9684 KB Output is correct
78 Correct 7 ms 9732 KB Output is correct
79 Correct 1252 ms 166116 KB Output is correct
80 Correct 3092 ms 853664 KB Output is correct
81 Correct 2003 ms 262844 KB Output is correct
82 Correct 2214 ms 99208 KB Output is correct
83 Correct 1891 ms 100004 KB Output is correct
84 Correct 1449 ms 104852 KB Output is correct
85 Correct 528 ms 103600 KB Output is correct
86 Correct 1229 ms 154332 KB Output is correct
87 Correct 3430 ms 886316 KB Output is correct
88 Correct 1262 ms 96884 KB Output is correct
89 Execution timed out 4065 ms 161828 KB Time limit exceeded
90 Halted 0 ms 0 KB -