Submission #966750

#TimeUsernameProblemLanguageResultExecution timeMemory
966750PM1Sprinkler (JOI22_sprinkler)C++17
83 / 100
4056 ms129680 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #define ll long long const int mxn=2e5+5; int n,M,q,st[mxn],fn[mxn],cnt,dis[mxn],par[mxn],w; int fnd[mxn][42][2]; vector<int>v[mxn],d[mxn]; struct segment{ vector<ll>val; int sz=0; void build(){ while(__builtin_popcount(sz)!=1){ sz++; } val.resize(sz*2,1); } void add(int i,int l,int r,int tl,int tr){ if(l>r||l>tr||r<tl||tl>tr){ return ; } if(l>=tl&&r<=tr){ val[i]*=w; val[i]%=M; return ; } int m=(l+r)>>1; add((i<<1),l,m,tl,tr); add((i<<1)^1,m+1,r,tl,tr); return ; } int get(int i){ if(i==0){ return 1; } int ret=val[i]*get((i>>1))%M; return ret; } }seg[mxn]; void dfs(int z){ st[z]=++cnt; d[dis[z]].push_back(st[z]); for(auto i:v[z]){ if(i!=par[z]){ par[i]=z; dis[i]=dis[z]+1; dfs(i); } } fn[z]=cnt; } void add(int x,int y){ if(d[x].size()==0)return; int l=fnd[y][x-dis[y]][0]; int r=fnd[y][x-dis[y]][1]; seg[x].add(1,0,seg[x].sz-1,l,r); } void up(int x,int dd){ for(;dd>=1 && x!=1;dd--){ int z=dis[x]+dd,zz=dis[x]+dd-1; add(z,x); add(zz,x); x=par[x]; } for(;dd>=0;dd--){ add(dis[x]+dd,x); } } void get(int z,int x){ int l=fnd[x][0][0]; cout<<seg[z].get(l+seg[z].sz)<<'\n'; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>M; for(int i=1;i<n;i++){ int x,y; cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } dfs(1); for(int i=0;i<=n;i++){ seg[i].sz=d[i].size(); seg[i].build(); } for(int i=1;i<=n;i++){ fnd[i][0][1]=fnd[i][0][0]=lower_bound(d[dis[i]].begin(),d[dis[i]].end(),st[i])-d[dis[i]].begin(); for(int j=1;j<=40 && dis[i]+j<mxn;j++){ int dd=dis[i]+j; fnd[i][j][0]=lower_bound(d[dd].begin(),d[dd].end(),st[i])-d[dd].begin(); fnd[i][j][1]=upper_bound(d[dd].begin(),d[dd].end(),fn[i])-d[dd].begin()-1; } } for(int i=1;i<=n;i++){ int l=fnd[i][0][0]; cin>>w; seg[dis[i]].add(1,0,seg[dis[i]].sz-1,l,l); } cin>>q; while(q--){ int ty,x,dd; cin>>ty; if(ty==1){ cin>>x>>dd>>w; up(x,dd); } else{ cin>>x; get(dis[x],x); } } 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...