Submission #1030980

#TimeUsernameProblemLanguageResultExecution timeMemory
1030980peraSprinkler (JOI22_sprinkler)C++17
0 / 100
4103 ms96496 KiB
#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 + 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 (stderr)

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()){
      |                   ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...