Submission #925924

#TimeUsernameProblemLanguageResultExecution timeMemory
925924andrei_boacaSprinkler (JOI22_sprinkler)C++17
0 / 100
3041 ms665792 KiB
#include <bits/stdc++.h> /*#pragma GCC optimize ("Ofast") #pragma GCC optimize ("fast-math") #pragma GCC optimize ("unroll-loops")*/ using namespace std; int n,mod,h[200005],root; vector<int> muchii[200005]; vector<int> kids[200005]; int d1[200005],dp[21][200005],in[200005],out[200005],timp; int use[200005],parent[200005],par[200005]; int nr[200005],where[200005]; vector<int> aib[2][200005][41]; /// 0 -> pref, 1 -> suf bool isancestor(int a,int b) { return in[a]<=in[b]&&out[a]>=out[b]; } int LCA(int a,int b) { if(d1[a]>d1[b]) swap(a,b); if(isancestor(a,b)) return a; for(int i=18;i>=0;i--) if(dp[i][a]!=0&&!isancestor(dp[i][a],b)) a=dp[i][a]; return dp[0][a]; } int dist(int a,int b) { int lca=LCA(a,b); return d1[a]+d1[b]-2*d1[lca]; } void build(int nod) { timp++; in[nod]=timp; for(int i=1;i<=20;i++) dp[i][nod]=dp[i-1][dp[i-1][nod]]; for(int i:muchii[nod]) if(i!=dp[0][nod]) { dp[0][i]=nod; d1[i]=d1[nod]+1; build(i); } out[nod]=timp; } void dfs1(int nod) { nr[nod]=1; for(int i:muchii[nod]) if(!use[i]&&i!=par[nod]) { par[i]=nod; dfs1(i); nr[nod]+=nr[i]; } } int centroid(int nod) { par[nod]=0; dfs1(nod); int lg=nr[nod]; int r=nod; while(true) { bool bad=0; for(int i:muchii[r]) if(!use[i]&&par[i]==r&&nr[i]>lg/2) { bad=1; par[r]=i; par[i]=0; nr[r]-=nr[i]; nr[i]+=nr[r]; r=i; break; } if(!bad) break; } use[r]=1; for(int i:muchii[r]) if(!use[i]) { int x=centroid(i); kids[r].push_back(x); } return r; } void dfs(int nod) { int cnt=0; for(int i:kids[nod]) { cnt++; where[i]=cnt; par[i]=nod; dfs(i); } int lg=kids[nod].size(); for(int i=0;i<=1;i++) for(int j=0;j<=40;j++) for(int k=0;k<=lg;k++) aib[i][j][nod].push_back(1); } int lsb(int x) { return x&(-x); } void update(int ind,int cur,int p1,int p2,int val) { int lg=kids[cur].size(); for(int i=p1;i<=40;i+=lsb(i)) for(int j=p2;j<=lg;j+=lsb(j)) aib[ind][i][cur][j]=(1LL*aib[ind][i][cur][j]*val)%mod; } int query(int ind,int cur,int p1,int p2) { int rez=1; for(int i=p1;i>=1;i-=lsb(i)) for(int j=p2;j>=1;j-=lsb(j)) rez=(1LL*rez*aib[ind][i][cur][j])%mod; return rez; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>mod; for(int i=1;i<n;i++) { int a,b; cin>>a>>b; muchii[a].push_back(b); muchii[b].push_back(a); } for(int i=1;i<=n;i++) cin>>h[i]; d1[1]=0; build(1); root=centroid(1); par[root]=0; dfs(root); /*for(int i=1;i<=n;i++) for(int j=0;j<=40;j++) add[i][j]=1;*/ int q; cin>>q; while(q--) { int tip; cin>>tip; if(tip==1) { int nod,d,val; cin>>nod>>d>>val; /*for(int i=1;i<=d;i++) add[nod][i]=(1LL*add[nod][i]*val)%mod;*/ update(1,nod,40-d+1,1,val); int cur=nod; int badind=0; while(cur!=0) { int dmax=d-dist(nod,cur); if(dmax>=0) h[cur]=(1LL*h[cur]*val)%mod; if(dmax>0&&badind!=0) { int lg=kids[cur].size(); update(1,cur,40-dmax+1,badind+1,val); update(0,cur,40-dmax+1,lg-badind+2,val); } badind=where[cur]; cur=par[cur]; } } if(tip==2) { int nod; cin>>nod; int ans=h[nod]; int badind=where[nod]; int cur=par[nod]; while(cur!=0) { int d=dist(nod,cur); if(d<=40) { int lg=kids[cur].size(); int val=query(1,cur,40-d+1,badind); ans=(1LL*ans*val)%mod; val=query(0,cur,40-d+1,lg-badind+1); ans=(1LL*ans*val)%mod; } badind=where[cur]; cur=par[cur]; } 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...