Submission #607308

#TimeUsernameProblemLanguageResultExecution timeMemory
607308AbdelmagedNourSprinkler (JOI22_sprinkler)C++17
100 / 100
790 ms95980 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("Ofast") using namespace std; const int N=(2e5)+60,D=42; int n,q,p[N]; long long mul[N][D],val[N],mod; vector<vector<int>>adj; void dfs(int v,int par){ p[v]=par; for(auto&u:adj[v]){ if(u==par)continue; dfs(u,v); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>mod; adj.resize(n+50); for(int i=1;i<n;i++){ int u,v; cin>>u>>v; u--;v--; adj[u].push_back(v); adj[v].push_back(u); } dfs(0,-1); int last=0; for(int i=n;i<=n+40;i++){ p[last]=i; last=i; } for(int i=0;i<=n+40;i++)for(int j=0;j<=40;j++)mul[i][j]=1; for(int i=0;i<n;i++)cin>>val[i]; cin>>q; while(q--){ int type; cin>>type; if(type==1){ long long x,d,w; cin>>x>>d>>w;x--; for(int j=d;j>=0;j--){ mul[x][j]=(mul[x][j]*w)%mod; if(j>0)mul[x][j-1]=(mul[x][j-1]*w)%mod; x=p[x]; } }else{ long long x,ans; cin>>x;x--; ans=val[x]; for(int j=0;j<=40;j++){ ans=(ans*mul[x][j])%mod; x=p[x]; } cout<<ans<<"\n"; } } return 0; }
#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...