Submission #925303

#TimeUsernameProblemLanguageResultExecution timeMemory
925303alexddSprinkler (JOI22_sprinkler)C++17
53 / 100
4038 ms116368 KiB
#include<bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") using namespace std; int n,phi; long long MOD; int aint[800005]; void build(int nod, int st, int dr) { aint[nod]=1; if(st==dr) return; int mij=(st+dr)/2; build(nod*2,st,mij); build(nod*2+1,mij+1,dr); } void upd(int nod, int st, int dr, int le, int ri, int newv) { if(le>ri) return; if(le==st && dr==ri) { aint[nod]=1LL*aint[nod]*newv%MOD; return; } int mij=(st+dr)/2; upd(nod*2,st,mij,le,min(mij,ri),newv); upd(nod*2+1,mij+1,dr,max(le,mij+1),ri,newv); } int qry(int nod, int st, int dr, int poz) { if(st==dr) return aint[nod]; int mij=(st+dr)/2; if(poz<=mij) return 1LL*qry(nod*2,st,mij,poz)*aint[nod]%MOD; else return 1LL*qry(nod*2+1,mij+1,dr,poz)*aint[nod]%MOD; } int aib0[200005]; int qry0(int poz) { int aux=0; for(int i=poz;i>0;i-=(i&(-i))) aux+=aib0[i]; return aux; } void upd0(int poz, int newv) { for(int i=poz;i<=n;i+=(i&(-i))) aib0[i]+=newv; } int h[200005]; vector<int> con[200005]; int parent[200005]; int tole[200005][45]; int tori[200005][45]; int cntd[200005]; int cntd2[200005]; int depth[200005]; int pos[200005]; int care[200005]; void dfs(int nod) { cntd[depth[nod]]++; for(auto adj:con[nod]) { if(adj!=parent[nod]) { depth[adj]=depth[nod]+1; parent[adj]=nod; dfs(adj); } } } void dfs2(int nod) { cntd2[depth[nod]]++; pos[nod] = cntd[depth[nod]-1] + cntd2[depth[nod]]; care[pos[nod]]=nod; //cout<<nod<<" "<<pos[nod]<<" pos\n"; for(int d=0;d<=42;d++) { tole[nod][d] = n+5; tori[nod][d] = -1; } tole[nod][0] = tori[nod][0] = pos[nod]; for(auto adj:con[nod]) { if(adj!=parent[nod]) { dfs2(adj); for(int d=1;d<=42;d++) { tole[nod][d] = min(tole[nod][d], tole[adj][d-1]); tori[nod][d] = max(tori[nod][d], tori[adj][d-1]); } } } } void faupd(int le, int ri, int newv) { if(le>ri) return; if(newv!=0) { if(ri-le+1 <= 30) { for(int i=le;i<=ri;i++) h[care[i]] = (1LL*h[care[i]]*newv)%MOD; } else upd(1,1,n,le,ri,newv); } else { upd0(le,1); upd0(ri+1,-1); } } int calc_phi(int x) { int d=2,prod=x; while(d*d<=x) { if(x%d==0) { while(x%d==0) x/=d; prod = prod / d * (d-1); } if(d==2) d--; d+=2; } if(x>1) prod = prod / x * (x-1); return prod; } int getrez(int poz) { if(qry0(poz)>0) return 0; else return qry(1,1,n,poz); } int le[200005],ri[200005]; signed main() { ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>MOD; phi = calc_phi(MOD); int a,b; for(int i=1;i<n;i++) { cin>>a>>b; con[a].push_back(b); con[b].push_back(a); } depth[1]=1; dfs(1); for(int i=2;i<=n;i++) cntd[i]+=cntd[i-1]; dfs2(1); for(int i=1;i<=n;i++) { cin>>h[i]; } build(1,1,n); int cntq,tip,d; cin>>cntq; for(int pas=1;pas<=cntq;pas++) { cin>>tip; if(tip==1) { cin>>a>>d>>b; int cur=a; for(int i=0;i<=d;i++) { if(cur==0) break; ///j > -1 + d - (i+1) int lim=0; if(parent[cur]!=0) lim=max(lim,d-i-1); for(int j=lim;j<=d-i;j++) { faupd(tole[cur][j],tori[cur][j],b); } cur = parent[cur]; } } else { cin>>a; cout<<(1LL*h[a]*getrez(pos[a]))%MOD<<"\n"; //cout<<h[a]<<" "<<qry_brut(pos[a])<<" zzz\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...