제출 #556020

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556020		600Mihnea	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	2429 ms	143436 KiB

sprinkler

#include <bits/stdc++.h>

bool home = 1;

using namespace std;

typedef long long ll;
const int N=200000+7;
const int K=20;
int n;
int q;
int mod;
int h[N];
vector<int> g[N];
pair<int, int> rmq[K][2*N];
int lg[2*N];
int par[N];
int dep[N];
int first_euler[N];
int last_euler[N];
vector<int> la[N];
int top;
int verts[N];
int pos[N];

void build(int a,int p=-1){
  par[a]=p;
  la[dep[a]].push_back(a);
  rmq[0][++top]={dep[a], a};
  first_euler[a]=last_euler[a]=top;
  for(auto&b:g[a]){
    if(b==p) continue;
    dep[b]=1+dep[a];
    build(b,a);
    rmq[0][++top]={dep[a], a};
    last_euler[a]=top;
  }

}

int get_lca(int a,int b){
  if(first_euler[a]>last_euler[b]) swap(a,b);
  a=first_euler[a];
  b=last_euler[b];
  assert(a<=b);
  int k=lg[b-a+1];
  return min(rmq[k][a],rmq[k][b-(1<<k)+1]).second;
}

int get_dist(int a,int b){
  int c=get_lca(a,b);
  return dep[a]+dep[b]-2*dep[c];
}

int cnt_at_dep_before(int dep,int when) {
  int low=0,high=(int)la[dep].size()-1,sol=0;
  while(low<=high){
    int mid=(low+high)/2;
    if(first_euler[la[dep][mid]]<=when){
      sol=mid+1;
      low=mid+1;
    }else{
      high=mid-1;
    }
  }
  return sol;
}

int delta[N];
const int MX=40;

int mlt[N][MX+1];

void mulup(int &a,int b){
  assert(0<=a&&a<mod);
  assert(0<=b&&b<mod);
  a=a*(ll)b%mod;
}

signed main() {
#ifdef ONLINE_JUDGE
  home = 0;
#endif

  for(int i=0;i<N;i++){
    for(int j=0;j<=MX;j++){
      mlt[i][j]=1;
    }
  }

  home=0;

  if (home) {
    freopen("I_am_iron_man", "r", stdin);
  }
  else {
    ios::sync_with_stdio(0); cin.tie(0);
  }

  cin>>n>>mod;

  for (int i=1;i<n;i++) {
    int a, b;
    cin>>a>>b;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  build(1);
  for(int i=2;i<=top;i++) lg[i]=1+lg[i/2];

  for (int k=1;(1<<k)<=top;k++) {
    for(int i=1;i+(1<<k)-1<=top;i++){
      rmq[k][i]=min(rmq[k-1][i],rmq[k-1][i+(1<<(k-1))]);
    }
  }
  {
    top=0;
    for (int d=0;d<=n;d++){
      delta[d]=top;
      for(auto &i:la[d]){
        verts[++top]=i;
        pos[i]=top;
      }
    }
    assert(top==n);
  }
  for (int i=1;i<=n;i++) {
    cin>>h[pos[i]];
  }
  cin>>q;
  while(q--){
    int type;
    cin>>type;
    assert(type==1||type==2);
    if(type==1){
      int x,d,w;
      cin>>x>>d>>w;

      vector<pair<int, int>> prs;

      int vertex=x;

      while (vertex>=1&&d>=0) {
        prs.push_back({vertex, d});
        vertex=par[vertex];
        d--;
      }

      reverse(prs.begin(),prs.end());

      int maxdep=-1;

      for (auto &it:prs){
        vertex=it.first;
        d=it.second;
        for(int h=dep[vertex];h<=dep[vertex]+d;h++){
          if(h>maxdep){
            maxdep=h;
            mulup(mlt[vertex][h-dep[vertex]],w);
          }
        }
      }

    }else{
      int x,xinit;
      cin>>x;
      int sol=h[pos[x]];
      int cur_dist=0;
      while (x>=1&&cur_dist<=MX){
        sol=sol*(ll)mlt[x][cur_dist]%mod;
        x=par[x];
        cur_dist++;
      }

      cout<<sol<<"\n";
    }
  }


}

컴파일 시 표준 에러 (stderr) 메시지

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:166:13: warning: unused variable 'xinit' [-Wunused-variable]
  166 |       int x,xinit;
      |             ^~~~~
sprinkler.cpp:94:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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