oj.uz

답안 #1030974

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1030974 2024-07-22T13:07:47 Z pera Sprinkler (JOI22_sprinkler) C++17
9 / 100
 1274 ms 113296 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;
      }
      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);
            }
         }
      }
   }
}
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:121:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  121 | main(){
      | ^~~~
sprinkler.cpp: In function 'void UPD(long long int, long long int, long long int)':
sprinkler.cpp:104:24: warning: 'posR' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |                if(posR + (1 << bit) < (int)E[depth].size()){
      |                   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 72276 KB Output is correct
2 Correct 29 ms 72432 KB Output is correct
3 Correct 30 ms 72276 KB Output is correct
4 Incorrect 32 ms 72528 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 72272 KB Output is correct
2 Correct 838 ms 89524 KB Output is correct
3 Correct 808 ms 98244 KB Output is correct
4 Correct 793 ms 106280 KB Output is correct
5 Correct 802 ms 97900 KB Output is correct
6 Correct 765 ms 96748 KB Output is correct
7 Correct 841 ms 97352 KB Output is correct
8 Correct 764 ms 97708 KB Output is correct
9 Correct 878 ms 113296 KB Output is correct
10 Correct 857 ms 111812 KB Output is correct
11 Correct 821 ms 97472 KB Output is correct
12 Correct 784 ms 98244 KB Output is correct
13 Correct 748 ms 99260 KB Output is correct
14 Correct 879 ms 98996 KB Output is correct
15 Correct 761 ms 97340 KB Output is correct
16 Correct 771 ms 97732 KB Output is correct
17 Correct 858 ms 97864 KB Output is correct
18 Correct 29 ms 72276 KB Output is correct
19 Correct 30 ms 72284 KB Output is correct
20 Correct 29 ms 72276 KB Output is correct
21 Correct 30 ms 72276 KB Output is correct
22 Correct 31 ms 72284 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 72272 KB Output is correct
2 Correct 838 ms 89524 KB Output is correct
3 Correct 808 ms 98244 KB Output is correct
4 Correct 793 ms 106280 KB Output is correct
5 Correct 802 ms 97900 KB Output is correct
6 Correct 765 ms 96748 KB Output is correct
7 Correct 841 ms 97352 KB Output is correct
8 Correct 764 ms 97708 KB Output is correct
9 Correct 878 ms 113296 KB Output is correct
10 Correct 857 ms 111812 KB Output is correct
11 Correct 821 ms 97472 KB Output is correct
12 Correct 784 ms 98244 KB Output is correct
13 Correct 748 ms 99260 KB Output is correct
14 Correct 879 ms 98996 KB Output is correct
15 Correct 761 ms 97340 KB Output is correct
16 Correct 771 ms 97732 KB Output is correct
17 Correct 858 ms 97864 KB Output is correct
18 Correct 29 ms 72276 KB Output is correct
19 Correct 30 ms 72284 KB Output is correct
20 Correct 29 ms 72276 KB Output is correct
21 Correct 30 ms 72276 KB Output is correct
22 Correct 31 ms 72284 KB Output is correct
23 Correct 29 ms 72284 KB Output is correct
24 Incorrect 825 ms 97476 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 72272 KB Output is correct
2 Incorrect 1274 ms 101968 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 72276 KB Output is correct
2 Incorrect 1209 ms 99264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 72276 KB Output is correct
2 Correct 29 ms 72432 KB Output is correct
3 Correct 30 ms 72276 KB Output is correct
4 Incorrect 32 ms 72528 KB Output isn't correct
5 Halted 0 ms 0 KB -