Submission #970626

#TimeUsernameProblemLanguageResultExecution timeMemory
970626MarwenElarbiSprinkler (JOI22_sprinkler)C++17
3 / 100
6 ms8796 KiB
#include <bits/stdc++.h> using namespace std; vector<int> adj[100005]; long long h[100005]; long long parent[100005]; long long mul[100005][45]; int mod; void dfs(int x,int p){ for(auto u:adj[x]){ if(u==p) continue; parent[u]=x; dfs(u,x); } return; } void update(int x,int d,int w){ if(d==-1)return; if(x==0){ for (int i = 0; i <= d; ++i) { mul[x][i]=mul[x][i]*w%mod; } //if(x==0) cout <<"nav"<<" "<<mul[0][0]<<endl; return; } update(parent[x],d-1,w); mul[x][d]=mul[x][d]*w%mod; if(d) mul[x][d-1]=mul[x][d-1]*w%mod; } long long query(int x) { long long ans=h[x]; int cur=x; for (int i = 0; i <= 40; ++i) { ans=ans*mul[cur][i]%mod; if(cur==0) return ans; cur=parent[cur]; } return ans; } int main() { int n; cin>>n>>mod; for (int i = 0; i < n-1; ++i) { int x,y; cin>>x>>y; x--;y--; adj[x].push_back(y); adj[y].push_back(x); } for (int i = 0; i < n; ++i) { for (int j = 0; j < 41; ++j) { mul[i][j]=1; } cin>>h[i]; } dfs(0,-1); int q; cin>>q; while(q--){ int c; cin>>c; if(c==1){ int x,d,w; cin>>x>>d>>w; x--; update(x,d,w); }else{ int x; cin>>x; x--; cout << query(x)<<endl; } } }
#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...