oj.uz

답안 #1030971

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1030971 2024-07-22T13:04:59 Z pera Sprinkler (JOI22_sprinkler) C++17
0 / 100
 1236 ms 96508 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
int n , M , Q , o = 0;
vector<int> t(4 * N) , lz(4 * N) , H(N) , in(N) , out(N) , d(N) , id(N) , up(N) , order = {0};
vector<vector<int>> g(N) , E(N) , D(N);
void dfs(int u , int p = 0){
   order.push_back(u);
   up[u] = p;
   in[u] = ++o;
   d[u] = d[p] + 1;
   E[d[u]].push_back(in[u]);
   if(u != 1){
      g[u].erase(find(g[u].begin() , g[u].end() , p));
   }
   for(int x = 0;x < (int)g[u].size();x ++){
      dfs(g[u][x] , u);
   }
   out[u] = o;
}
void build(int u , int l , int r){
   t[u] = lz[u] = 1;
   if(l != r){
      int m = (l + r) / 2;
      build(u * 2 , l , m);
      build(u * 2 + 1 , m + 1 , r);
   }
}
void push(int u){
   t[u * 2] = t[u * 2] * lz[u] % M;
   t[u * 2 + 1] = t[u * 2 + 1] * lz[u] % M;
   lz[u * 2] = lz[u * 2] * lz[u] % M;
   lz[u * 2 + 1] = lz[u * 2 + 1] * lz[u] % M;
   lz[u] = 1;
}
void upd(int u , int l , int r , int L , int R , int w){
   if(l > r || r < L || l > R){
      return ;
   }
   if(L <= l && r <= R){
      int bf = t[u];
      t[u] = t[u] * w % M;
      lz[u] = lz[u] * w % M;
      return;
   }
   int m = (l + r) / 2;
   push(u);
   upd(u * 2 , l , m , L , R , w);
   upd(u * 2 + 1 , m + 1 , r , L , R , w);
}
int get(int u , int l , int r , int pos){
   if(l == r){
      return t[u];
   }
   int m = (l + r) / 2;
   push(u);
   if(pos <= m){
      return get(u * 2 , l , m , pos);
   }
   return get(u * 2 + 1 , m + 1 , r , pos);
}
int GET(int u){
   return get(1 , 1 , n , id[u]);
}
void UPD(int u , int x , int W){
   for(int depth = d[u];depth <= min(d[u] + x , n);depth ++){
      //[in[u] , out[u]] -> id[first] , id[last];
      int L = -1 , R = -1;
      for(int bit = 20;bit >= 0;bit --){
         if(L + (1 << bit) < (int)E[depth].size()){
            if(E[depth][L + (1 << bit)] < in[u]){
               L += (1 << bit);
            }
         }
         if(R + (1 << bit) < (int)E[depth].size()){
            if(E[depth][R + (1 << bit)] <= out[u]){
               R += (1 << bit);
            }
         }
      }
      ++L;
      if(0 <= min(L , R) && max(L , R) < (int)E[depth].size() && in[u] <= min(E[depth][L] , E[depth][R]) && max(E[depth][L] , E[depth][R]) <= out[u] && L <= R){
         upd(1 , 1 , n , D[depth][L] , D[depth][R] , W);
      }
   }
   if(u != 1){
      int cnt = x , v = u , lst;
      while(v != 1 && cnt > 0){
         H[up[v]] = H[up[v]] * W % M;
         lst = v;
         v = up[v];
         --cnt;
      }
      if(v == 1 && cnt > 0){
         for(int depth = 2;depth <= cnt + 1;depth ++){
            int posL = -1 , posR;
            for(int bit = 20;bit >= 0;bit --){
               if(posL + (1 << bit) < (int)E[depth].size()){
                  if(E[depth][posL + (1 << bit)] < in[lst]){
                     posL += (1 << bit);
                  }
               }
               if(posR + (1 << bit) < (int)E[depth].size()){
                  if(E[depth][posR + (1 << bit)] <= out[lst]){
                     posR += (1 << bit);
                  }
               }
            }
            ++posR;
            if(posL >= 0){
               upd(1 , 1 , n , D[depth][0] , D[depth][posL] , W);
            }
            if(posR < (int)E[depth].size()){
               upd(1 , 1 , n , D[depth][posR] , D[depth].back() , W);
            }
         }
      }
   }
}
int main(){
   cin >> n >> M;
   for(int i = 1;i < n;i ++){
      int u , v;
      cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   dfs(1);
   build(1 , 1 , n);
   o = 0;
   for(int a = 1;a <= n;a ++){
      for(int x : E[a]){
         id[order[x]] = ++o;
         D[a].push_back(id[order[x]]);
      }
   }
   for(int i = 1;i <= n;i ++){
      cin >> H[i];
   }
   cin >> Q;
   while(Q--){
      int e;
      cin >> e;
      if(e == 1){
         int x , d , W;
         cin >> x >> d >> W;
         UPD(x , d , W);
      }else{
         int x;
         cin >> x; 
         cout << H[x] * GET(x) % M << endl;
      }
   }
}

Compilation message

sprinkler.cpp: In function 'void upd(int, int, int, int, int, int)':
sprinkler.cpp:41:11: warning: unused variable 'bf' [-Wunused-variable]
   41 |       int bf = t[u];
      |           ^~
sprinkler.cpp: In function 'void UPD(int, int, int)':
sprinkler.cpp:103:24: warning: 'posR' may be used uninitialized in this function [-Wmaybe-uninitialized]
  103 |                if(posR + (1 << bit) < (int)E[depth].size()){
      |                   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 28 ms 51192 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25436 KB Output is correct
2 Incorrect 855 ms 46812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25436 KB Output is correct
2 Incorrect 855 ms 46812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 25436 KB Output is correct
2 Incorrect 1236 ms 54320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25436 KB Output is correct
2 Runtime error 347 ms 96508 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 28 ms 51192 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -