Submission #556021

#	Time	Username	Problem	Language	Result	Execution time	Memory
556021		600Mihnea	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	2375 ms	62572 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];
int par[N];
int dep[N];

void build(int a,int p=-1){
  par[a]=p;
  for(auto&b:g[a]){
    if(b==p) continue;
    dep[b]=1+dep[a];
    build(b,a);
  }

}


const int MX=40;

int mlt[N][MX+1];

void mulup(int &a,int b){
  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=1;i<=n;i++) {
    cin>>h[i];
  }
  cin>>q;
  while(q--){
    int type;
    cin>>type;
    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[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";
    }
  }


}

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:105:13: warning: unused variable 'xinit' [-Wunused-variable]
  105 |       int x,xinit;
      |             ^~~~~
sprinkler.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     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