oj.uz

Submission #615353

# Submission time Handle Problem Language Result Execution time Memory
615353 2022-07-31T08:32:47 Z 반딧불(#8492) Sprinkler (JOI22_sprinkler) C++17
0 / 100
 17 ms 19548 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(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> 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++) cin>>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;
        cin>>qt;
        if(qt==1){
            int x, d, dp; ll w;
            cin>>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;
            cin>>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);
            }
            cout<<tree.query(1, 1, n, in[x])<<'\n';
        }
    }
}

Compilation message

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
sprinkler.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 19516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 19540 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 19540 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 19524 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 19548 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 19516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -