oj.uz

Submission #615381

# Submission time Handle Problem Language Result Execution time Memory
615381 2022-07-31T08:43:57 Z 반딧불(#8492) Sprinkler (JOI22_sprinkler) C++17
41 / 100
 4000 ms 886248 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];

    void init(int i, int l, int r){
        tree[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 update(int i, int l, int r, int s, int e, ll v){
        if(s<=l && r<=e){
            tree[i] = (tree[i] * v) % MOD;
            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){
        if(l==r) return tree[i];
        int m = (l+r)>>1;
        if(x<=m) return (tree[i] * query(i*2, l, m, x)) % MOD;
        else return (tree[i] * query(i*2+1, m+1, r, x)) % MOD;
    }
} 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:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%d %lld", &n, &MOD);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
sprinkler.cpp:91:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~
sprinkler.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
sprinkler.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         scanf("%d", &qt);
      |         ~~~~~^~~~~~~~~~~
sprinkler.cpp:109:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |             scanf("%d %d %lld", &x, &d, &w);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:137:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9664 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 10580 KB Output is correct
5 Correct 10 ms 10232 KB Output is correct
6 Correct 9 ms 10196 KB Output is correct
7 Correct 8 ms 10196 KB Output is correct
8 Correct 7 ms 10160 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 7 ms 9664 KB Output is correct
12 Correct 5 ms 9756 KB Output is correct
13 Correct 6 ms 9744 KB Output is correct
14 Correct 6 ms 9684 KB Output is correct
15 Correct 6 ms 9744 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Correct 6 ms 9684 KB Output is correct
18 Correct 6 ms 9720 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 6 ms 9684 KB Output is correct
21 Correct 7 ms 9684 KB Output is correct
22 Correct 5 ms 9680 KB Output is correct
23 Correct 6 ms 9684 KB Output is correct
24 Correct 7 ms 9684 KB Output is correct
25 Correct 7 ms 9684 KB Output is correct
26 Correct 7 ms 9684 KB Output is correct
27 Correct 6 ms 9720 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 9748 KB Output is correct
2 Correct 501 ms 94376 KB Output is correct
3 Correct 715 ms 93404 KB Output is correct
4 Correct 739 ms 110604 KB Output is correct
5 Correct 597 ms 92844 KB Output is correct
6 Correct 593 ms 92604 KB Output is correct
7 Correct 575 ms 92880 KB Output is correct
8 Correct 543 ms 94908 KB Output is correct
9 Correct 609 ms 112336 KB Output is correct
10 Correct 774 ms 130884 KB Output is correct
11 Correct 545 ms 94308 KB Output is correct
12 Correct 650 ms 93788 KB Output is correct
13 Correct 577 ms 104496 KB Output is correct
14 Correct 560 ms 98928 KB Output is correct
15 Correct 562 ms 94312 KB Output is correct
16 Correct 636 ms 92964 KB Output is correct
17 Correct 566 ms 92588 KB Output is correct
18 Correct 6 ms 9716 KB Output is correct
19 Correct 8 ms 9644 KB Output is correct
20 Correct 7 ms 9684 KB Output is correct
21 Correct 6 ms 9684 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 9748 KB Output is correct
2 Correct 501 ms 94376 KB Output is correct
3 Correct 715 ms 93404 KB Output is correct
4 Correct 739 ms 110604 KB Output is correct
5 Correct 597 ms 92844 KB Output is correct
6 Correct 593 ms 92604 KB Output is correct
7 Correct 575 ms 92880 KB Output is correct
8 Correct 543 ms 94908 KB Output is correct
9 Correct 609 ms 112336 KB Output is correct
10 Correct 774 ms 130884 KB Output is correct
11 Correct 545 ms 94308 KB Output is correct
12 Correct 650 ms 93788 KB Output is correct
13 Correct 577 ms 104496 KB Output is correct
14 Correct 560 ms 98928 KB Output is correct
15 Correct 562 ms 94312 KB Output is correct
16 Correct 636 ms 92964 KB Output is correct
17 Correct 566 ms 92588 KB Output is correct
18 Correct 6 ms 9716 KB Output is correct
19 Correct 8 ms 9644 KB Output is correct
20 Correct 7 ms 9684 KB Output is correct
21 Correct 6 ms 9684 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 6 ms 9684 KB Output is correct
24 Correct 514 ms 94300 KB Output is correct
25 Correct 730 ms 95080 KB Output is correct
26 Correct 738 ms 119980 KB Output is correct
27 Correct 635 ms 93008 KB Output is correct
28 Correct 691 ms 92868 KB Output is correct
29 Correct 641 ms 92748 KB Output is correct
30 Correct 565 ms 97080 KB Output is correct
31 Correct 677 ms 108752 KB Output is correct
32 Correct 885 ms 148828 KB Output is correct
33 Correct 533 ms 94448 KB Output is correct
34 Correct 762 ms 94560 KB Output is correct
35 Correct 6 ms 9684 KB Output is correct
36 Correct 8 ms 9692 KB Output is correct
37 Correct 7 ms 9684 KB Output is correct
38 Correct 7 ms 9728 KB Output is correct
39 Correct 6 ms 9764 KB Output is correct
40 Correct 7 ms 9684 KB Output is correct
41 Correct 5 ms 9684 KB Output is correct
42 Correct 7 ms 9680 KB Output is correct
43 Correct 6 ms 9684 KB Output is correct
44 Correct 8 ms 9684 KB Output is correct
45 Correct 7 ms 9684 KB Output is correct
46 Correct 6 ms 9684 KB Output is correct
47 Correct 7 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 6 ms 9684 KB Output is correct
2 Correct 1258 ms 162016 KB Output is correct
3 Correct 3079 ms 849436 KB Output is correct
4 Correct 1703 ms 258748 KB Output is correct
5 Correct 1918 ms 95116 KB Output is correct
6 Correct 1508 ms 95912 KB Output is correct
7 Correct 1154 ms 100732 KB Output is correct
8 Correct 586 ms 99484 KB Output is correct
9 Correct 1315 ms 150180 KB Output is correct
10 Correct 3384 ms 882184 KB Output is correct
11 Correct 1116 ms 92884 KB Output is correct
12 Execution timed out 4022 ms 158296 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 1195 ms 150572 KB Output is correct
3 Correct 3355 ms 864796 KB Output is correct
4 Correct 1645 ms 245912 KB Output is correct
5 Correct 1678 ms 98336 KB Output is correct
6 Correct 1309 ms 101172 KB Output is correct
7 Correct 1213 ms 100800 KB Output is correct
8 Correct 500 ms 99628 KB Output is correct
9 Correct 1109 ms 163112 KB Output is correct
10 Correct 3205 ms 886248 KB Output is correct
11 Correct 1065 ms 95464 KB Output is correct
12 Correct 3570 ms 134120 KB Output is correct
13 Execution timed out 4018 ms 154968 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9664 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 10580 KB Output is correct
5 Correct 10 ms 10232 KB Output is correct
6 Correct 9 ms 10196 KB Output is correct
7 Correct 8 ms 10196 KB Output is correct
8 Correct 7 ms 10160 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 7 ms 9664 KB Output is correct
12 Correct 5 ms 9756 KB Output is correct
13 Correct 6 ms 9744 KB Output is correct
14 Correct 6 ms 9684 KB Output is correct
15 Correct 6 ms 9744 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Correct 6 ms 9684 KB Output is correct
18 Correct 6 ms 9720 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 6 ms 9684 KB Output is correct
21 Correct 7 ms 9684 KB Output is correct
22 Correct 5 ms 9680 KB Output is correct
23 Correct 6 ms 9684 KB Output is correct
24 Correct 7 ms 9684 KB Output is correct
25 Correct 7 ms 9684 KB Output is correct
26 Correct 7 ms 9684 KB Output is correct
27 Correct 6 ms 9720 KB Output is correct
28 Correct 6 ms 9684 KB Output is correct
29 Correct 5 ms 9748 KB Output is correct
30 Correct 501 ms 94376 KB Output is correct
31 Correct 715 ms 93404 KB Output is correct
32 Correct 739 ms 110604 KB Output is correct
33 Correct 597 ms 92844 KB Output is correct
34 Correct 593 ms 92604 KB Output is correct
35 Correct 575 ms 92880 KB Output is correct
36 Correct 543 ms 94908 KB Output is correct
37 Correct 609 ms 112336 KB Output is correct
38 Correct 774 ms 130884 KB Output is correct
39 Correct 545 ms 94308 KB Output is correct
40 Correct 650 ms 93788 KB Output is correct
41 Correct 577 ms 104496 KB Output is correct
42 Correct 560 ms 98928 KB Output is correct
43 Correct 562 ms 94312 KB Output is correct
44 Correct 636 ms 92964 KB Output is correct
45 Correct 566 ms 92588 KB Output is correct
46 Correct 6 ms 9716 KB Output is correct
47 Correct 8 ms 9644 KB Output is correct
48 Correct 7 ms 9684 KB Output is correct
49 Correct 6 ms 9684 KB Output is correct
50 Correct 6 ms 9684 KB Output is correct
51 Correct 6 ms 9684 KB Output is correct
52 Correct 514 ms 94300 KB Output is correct
53 Correct 730 ms 95080 KB Output is correct
54 Correct 738 ms 119980 KB Output is correct
55 Correct 635 ms 93008 KB Output is correct
56 Correct 691 ms 92868 KB Output is correct
57 Correct 641 ms 92748 KB Output is correct
58 Correct 565 ms 97080 KB Output is correct
59 Correct 677 ms 108752 KB Output is correct
60 Correct 885 ms 148828 KB Output is correct
61 Correct 533 ms 94448 KB Output is correct
62 Correct 762 ms 94560 KB Output is correct
63 Correct 6 ms 9684 KB Output is correct
64 Correct 8 ms 9692 KB Output is correct
65 Correct 7 ms 9684 KB Output is correct
66 Correct 7 ms 9728 KB Output is correct
67 Correct 6 ms 9764 KB Output is correct
68 Correct 7 ms 9684 KB Output is correct
69 Correct 5 ms 9684 KB Output is correct
70 Correct 7 ms 9680 KB Output is correct
71 Correct 6 ms 9684 KB Output is correct
72 Correct 8 ms 9684 KB Output is correct
73 Correct 7 ms 9684 KB Output is correct
74 Correct 6 ms 9684 KB Output is correct
75 Correct 7 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 6 ms 9684 KB Output is correct
79 Correct 1258 ms 162016 KB Output is correct
80 Correct 3079 ms 849436 KB Output is correct
81 Correct 1703 ms 258748 KB Output is correct
82 Correct 1918 ms 95116 KB Output is correct
83 Correct 1508 ms 95912 KB Output is correct
84 Correct 1154 ms 100732 KB Output is correct
85 Correct 586 ms 99484 KB Output is correct
86 Correct 1315 ms 150180 KB Output is correct
87 Correct 3384 ms 882184 KB Output is correct
88 Correct 1116 ms 92884 KB Output is correct
89 Execution timed out 4022 ms 158296 KB Time limit exceeded
90 Halted 0 ms 0 KB -