oj.uz

Submission #615066

# Submission time Handle Problem Language Result Execution time Memory
615066 2022-07-31T06:30:36 Z 반딧불(#8492) Sprinkler (JOI22_sprinkler) C++17
12 / 100
 2466 ms 102988 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll MOD;

ll mpow(ll x, ll y){
    if(y==0) return 1;
    if(y&1) return mpow(x, y-1)*x%MOD;
    ll tmp = mpow(x, y/2);
    return tmp*tmp%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(lazy[i]==1) return;
        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;

struct Fenwick{
    int n;
    int tree[200002];

    void init(int _n){
        n = _n;
        for(int i=0; i<=n; i++) tree[i] = 0;
    }

    void add(int x, int v){
        while(x<=n){
            tree[x] += v;
            x += x&-x;
        }
    }

    int sum(int x){
        int ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }
} fenwick;

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];

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]);
    fenwick.init(n);
    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; ll w;
            scanf("%d %d %lld", &x, &d, &w);
            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;
                fenwick.add(treeL[i], 1);
                fenwick.add(treeR[i]+1, -1);
//                tree.update(1, 1, n, treeL[i], treeR[i], w);
            }
        }
        else{
            int x;
            scanf("%d", &x);
            if(fenwick.sum(in[x])) puts("0");
            else printf("%lld\n", arr[x]);
//            printf("%lld\n", tree.query(1, 1, n, in[x]));
        }
    }
}

Compilation message

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

Subtask #1
0 / 3.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 29.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 688 ms 98308 KB Output is correct
3 Correct 2327 ms 93992 KB Output is correct
4 Correct 1076 ms 96656 KB Output is correct
5 Correct 920 ms 84692 KB Output is correct
6 Correct 870 ms 89928 KB Output is correct
7 Correct 700 ms 90188 KB Output is correct
8 Correct 540 ms 91288 KB Output is correct
9 Correct 792 ms 100780 KB Output is correct
10 Correct 2466 ms 102988 KB Output is correct
11 Correct 628 ms 90296 KB Output is correct
12 Correct 2029 ms 89428 KB Output is correct
13 Correct 1952 ms 90272 KB Output is correct
14 Correct 1856 ms 90840 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct

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 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -