oj.uz

Submission #1030984

# Submission time Handle Problem Language Result Execution time Memory
1030984 2024-07-22T13:13:29 Z pera Sprinkler (JOI22_sprinkler) C++17
9 / 100
 4000 ms 105152 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5 + 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;
         for(int depth = d[v] + 1;depth <= d[v] + cnt;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);
            }
         }
      }
   }
}
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(long long int, long long int, long long int, long long int, long long int, long long int)':
sprinkler.cpp:42:11: warning: unused variable 'bf' [-Wunused-variable]
   42 |       int bf = t[u];
      |           ^~
sprinkler.cpp: At global scope:
sprinkler.cpp:119:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  119 | main(){
      | ^~~~
sprinkler.cpp: In function 'void UPD(long long int, long long int, long long int)':
sprinkler.cpp:102:24: warning: 'posR' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |                if(posR + (1 << bit) < (int)E[depth].size()){
      |                   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 72272 KB Output is correct
2 Correct 28 ms 72284 KB Output is correct
3 Correct 28 ms 72276 KB Output is correct
4 Incorrect 45 ms 72540 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 72272 KB Output is correct
2 Correct 773 ms 89472 KB Output is correct
3 Correct 756 ms 86392 KB Output is correct
4 Correct 783 ms 96192 KB Output is correct
5 Correct 758 ms 88004 KB Output is correct
6 Correct 704 ms 86824 KB Output is correct
7 Correct 675 ms 87232 KB Output is correct
8 Correct 694 ms 87356 KB Output is correct
9 Correct 846 ms 105152 KB Output is correct
10 Correct 766 ms 100152 KB Output is correct
11 Correct 854 ms 89384 KB Output is correct
12 Correct 684 ms 86208 KB Output is correct
13 Correct 776 ms 88012 KB Output is correct
14 Correct 729 ms 87060 KB Output is correct
15 Correct 677 ms 85776 KB Output is correct
16 Correct 695 ms 86060 KB Output is correct
17 Correct 701 ms 86328 KB Output is correct
18 Correct 29 ms 72372 KB Output is correct
19 Correct 30 ms 72272 KB Output is correct
20 Correct 28 ms 72280 KB Output is correct
21 Correct 28 ms 72308 KB Output is correct
22 Correct 28 ms 72284 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 72272 KB Output is correct
2 Correct 773 ms 89472 KB Output is correct
3 Correct 756 ms 86392 KB Output is correct
4 Correct 783 ms 96192 KB Output is correct
5 Correct 758 ms 88004 KB Output is correct
6 Correct 704 ms 86824 KB Output is correct
7 Correct 675 ms 87232 KB Output is correct
8 Correct 694 ms 87356 KB Output is correct
9 Correct 846 ms 105152 KB Output is correct
10 Correct 766 ms 100152 KB Output is correct
11 Correct 854 ms 89384 KB Output is correct
12 Correct 684 ms 86208 KB Output is correct
13 Correct 776 ms 88012 KB Output is correct
14 Correct 729 ms 87060 KB Output is correct
15 Correct 677 ms 85776 KB Output is correct
16 Correct 695 ms 86060 KB Output is correct
17 Correct 701 ms 86328 KB Output is correct
18 Correct 29 ms 72372 KB Output is correct
19 Correct 30 ms 72272 KB Output is correct
20 Correct 28 ms 72280 KB Output is correct
21 Correct 28 ms 72308 KB Output is correct
22 Correct 28 ms 72284 KB Output is correct
23 Correct 28 ms 72284 KB Output is correct
24 Incorrect 785 ms 88768 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 72276 KB Output is correct
2 Incorrect 2528 ms 101916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 72272 KB Output is correct
2 Execution timed out 4061 ms 97116 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 72272 KB Output is correct
2 Correct 28 ms 72284 KB Output is correct
3 Correct 28 ms 72276 KB Output is correct
4 Incorrect 45 ms 72540 KB Output isn't correct
5 Halted 0 ms 0 KB -