제출 #1216407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1216407		noyancanturk	Sprinkler (JOI22_sprinkler)	C++20	0 / 100	1094 ms	1114112 KiB

sprinkler

#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back

int mod;
int mul(int i,int j){
  return i*j%mod;
}

struct fenw{
  signed*tree[42];
  int n,m;
  void init(int M){
    n=41,m=M;
    for(int i=1;i<=n;i++){
      tree[i]=new signed[n+1];
      for(int j=1;j<=m;j++)tree[i][j]=1;
    }
  }
  void update(int x,int y,int val){
    x++;
    for(int i=x;i<=n;i+=i&-i){
      for(int j=y;j<=m;j+=j&-j){
        tree[i][j]=mul(tree[i][j],val);
      }
    }
  }
  int query(int x,int y){
    x++;
    int ans=1;
    for(int i=x;i;i-=i&-i){
      for(int j=y;j;j-=j&-j){
        ans=mul(tree[i][j],ans);
      }
    }
    return ans;
  }
};


const int lim=2e5+100;
vector<int>v[lim];

int tot;

bool vis[lim];
int sz[lim];
int dis[18][lim];
int col[18][lim];
int parent[lim];
int layer[lim];
fenw fw[lim][2];

int sbs(int node,int par,int dep){
  dis[dep][node]=par?(dis[dep][par]+1):0;
  sz[node]=1;
  for(int j:v[node]){
    if(vis[j]||j==par)continue;
    sz[node]+=sbs(j,node,dep);
  }
  return sz[node];
}

int findcen(int node,int par){
  for(int j:v[node]){
    if(vis[j]||j==par)continue;
    if(tot<2*sz[j])return findcen(j,node);
  }
  return node;
}

void color(int node,int par,int dep,int code){
  col[dep][node]=code;
  for(int j:v[node]){
    if(vis[j]||j==par)continue;
    color(j,node,dep,code);
  }
}

void decomp(int node,int par,int dep=0){
  tot=sbs(node,0,dep);
  int cent=findcen(node,0);
  sbs(cent,0,dep);
  vis[cent]=1;
  layer[cent]=dep;
  parent[cent]=par;
  int code=0;
  for(int j:v[cent]){
    if(vis[j])continue;
    color(j,cent,dep,++code);
  }
  fw[cent][0].init(code);
  fw[cent][1].init(code);
  for(int j:v[cent]){
    if(vis[j])continue;
    decomp(j,cent,dep+1);
  }
}

int h[lim];
int applied[lim][41];

void update(int node,int ds,int val){
  h[node]=mul(h[node],val);
  for(int i=0;i<=ds;i++){
    applied[node][i]=mul(applied[node][i],val);
  }
  int curdep=layer[node],curnode=node;
  while(1){
    if(node==curnode){

    }else if(dis[curdep][node]<=ds){
      fw[curnode][0].update(40-ds+dis[curdep][node],col[curdep][node],val);
      fw[curnode][1].update(40-ds+dis[curdep][node],fw[curnode][1].m-col[curdep][node]+1,val);
    }
    if(!layer[curnode])break;
    curdep--;
    curnode=parent[curnode];
  }
}

int query(int node){
  int ans=h[node];
  int curdep=layer[node],curnode=node;
  while(1){
    if(node==curnode){
      ans=mul(ans,fw[curnode][0].query(40,fw[curnode][0].m));
    }else if(dis[curdep][node]<=40){
      ans=mul(ans,applied[curnode][dis[curdep][node]]);
      ans=mul(ans,fw[curnode][0].query(40-dis[curdep][node],col[curdep][node]-1));
      ans=mul(ans,fw[curnode][1].query(40-dis[curdep][node],fw[curnode][1].m-col[curdep][node]));
    }
    if(!layer[curnode]||!ans)break;
    curdep--;
    curnode=parent[curnode];
  }
  return ans;
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n;
  cin>>n>>mod;
  for(int i=0;i<n-1;i++){
    int x,y;
    cin>>x>>y;
    v[x].pb(y);
    v[y].pb(x);
  }
  for(int i=1;i<=n;i++){
    cin>>h[i];
    for(int j=0;j<=40;j++){
      applied[i][j]=1;
    }
  }
  decomp(1,0);
  int q;
  cin>>q;
  while(q--){
    int ty;
    cin>>ty;
    if(ty==1){
      int x,d,w;
      cin>>x>>d>>w;
      update(x,d,w);
    }else{
      int node;
      cin>>node;
      cout<<query(node)<<'\n';
    }
  }
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17