Submission #890718

#TimeUsernameProblemLanguageResultExecution timeMemory
890718Ahmed57Sprinkler (JOI22_sprinkler)C++17
3 / 100
4093 ms619304 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int dp[200001][41]; int lo[200001][41]; int P[200001],dep[200001]; int Pr[200001][41]; int cnt = 1,n,L; map<int,int> mp[200001]; vector<int> adj[200001]; int h[200001],sz[200001]; int vis[200001],ma[200001],mi[200001]; map<pair<int,int>,int> getIndex; int dfs(int i,int pr){ sz[i] = 1; for(auto j:adj[i]){ if(j==pr||vis[j])continue; sz[i]+=dfs(j,i); } return sz[i]; } int getCen(int i,int pr,int ss){ for(auto j:adj[i]){ if(j==pr||vis[j])continue; if(sz[j]*2>ss)return getCen(j,i,ss); } return i; } void lol(int i,int pr,int co,int de){ mp[de][i] = co; for(auto j:adj[i]){ if(j==pr||vis[j])continue; lol(j,i,co,de); } } void centroid(int i,int pr){ int cen = getCen(i,i,dfs(i,i)); vis[cen] = 1; P[cen] = pr; mi[cen] =cnt; for(auto j:adj[cen]){ if(vis[j])continue; lol(j,cen,j,cen); getIndex[{cen,j}] = cnt++; } ma[cen] = cnt-1; for(auto j:adj[cen]){ if(vis[j])continue; centroid(j,cen); } } void init(int i,int pr){ Pr[i][0] = pr; dep[i] = dep[pr]+1; for(int j = 1;j<19;j++){ Pr[i][j] = Pr[Pr[i][j-1]][j-1]; } for(auto j:adj[i]){ if(j==pr)continue; init(j,i); } } int lca(int a,int b){ int sum = dep[a]+dep[b]; if(dep[a]<dep[b])swap(a,b); for(int j = 18;j>=0;j--){ if(dep[Pr[a][j]]>=dep[b])a = Pr[a][j]; } if(a==b){ return sum-2*dep[a]; } for(int j = 18;j>=0;j--){ if(Pr[a][j]!=Pr[b][j]){ a = Pr[a][j]; b = Pr[b][j]; } } return sum-2*dep[Pr[a][0]]; } int seg[800001][41]; void build(int p,int l,int r){ if(l==r){ for(int j = 0;j<=40;j++){ seg[p][j] = 1; } return ; } int md = (l+r)/2; build(p*2,l,md);build(p*2+1,md+1,r); for(int j = 0;j<=40;j++){ seg[p][j] = seg[p*2][j]*seg[p*2+1][j]; } return ; } void update(int p,int l,int r,int idx,int val,int ty){ if(l==r){ seg[p][ty]*=val;seg[p][ty]%=L;return ; } int md = (l+r)/2; if(idx<=md)update(p*2,l,md,idx,val,ty); else update(p*2+1,md+1,r,idx,val,ty); seg[p][ty] = (seg[p*2][ty]*seg[p*2+1][ty])%L; } int query(int p,int l,int r,int lq,int rq,int ty){ if(r<lq||l>rq||lq>rq)return 1; if(l>=lq&&r<=rq){ return seg[p][ty]; } int md = (l+r)/2; return (query(p*2,l,md,lq,rq,ty)*query(p*2+1,md+1,r,lq,rq,ty))%L; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); //freopen("input.txt","r",stdin); //freopen("outout.txt","w",stdout); cin>>n>>L; for(int i = 0;i<n-1;i++){ int a,b;cin>>a>>b; adj[a].push_back(b); adj[b].push_back(a); } for(int i = 1;i<=n;i++){ cin>>h[i]; } //cout<<"hhh"<<endl; init(1,1); //cout<<"hhh"<<endl; build(1,1,n); centroid(1,-1); //cout<<cnt<<endl; for(int i = 1;i<=n;i++){ for(int j = 0;j<=40;j++)dp[i][j] = 1; if(i<=cnt){ for(int j = 0;j<=40;j++)lo[i-1][j] = 1; } } //cout<<"hhh"<<endl; int q;cin>>q; while(q--){ int ty;cin>>ty; if(ty==1){ int x,d,v; cin>>x>>d>>v; int org = x; for(int j = 0;j<=d;j++){dp[x][j]*=v;dp[x][j]%=L;} while(P[x]!=-1){ x = P[x]; int w = mp[x][org]; int id = getIndex[{x,w}]; //cout<<x<<"x"<<q<<" "<<id<<endl; int le = lca(x,org); if(le<=d){ for(int j = 0;j<=d-le;j++){ update(1,1,n,id,v,j); } } } }else{ int x;cin>>x; long long all = (h[x]*(mi[x]==0?1:query(1,1,n,mi[x],ma[x],0)))%L; all*=dp[x][0];all%=L; //cout<<all<<"pp"<<endl; int org = x; while(P[x]!=-1){ x = P[x]; int w = mp[x][org]; int id = getIndex[{x,w}]; //cout<<x<<"hhh "<<id<<endl; int le = lca(x,org); if(le<=40){all*=query(1,1,n,mi[x],id-1,le);all%=L;} if(le<=40){all*=query(1,1,n,id+1,ma[x],le);all%=L;} if(le<=40){all*=dp[x][le];all%=L;} //cout<<ma[x]<<endl; //cout<<dp[x][le]<<" "<<query(1,1,n,mi[x],id-1,le)<<" "<<query(1,1,n,id+1,ma[x],le)<<endl; } cout<<all<<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...