Submission #1022382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022382		NintsiChkhaidze	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1114 ms	104348 KiB

sprinkler

#include <bits/stdc++.h>
#include <ostream>
#define pb push_back
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define ll long long
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
#define int ll
using namespace std;
 
const int N = 3e5 + 5;
int mod,par[N],h[N],a[N][45];
vector <int> v[N];

void dfs(int x,int parent){
  par[x] = parent;
  for (int to: v[x]){
    if (to == parent) continue;
    dfs(to,x);
  }
}

signed main() {
  ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
  
  int n;
  cin>>n>>mod;

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

  for (int i = n + 45; i >= n + 1; i--){
    v[i].pb(i - 1);
  }

  dfs(n + 45,0);
  for (int i= 1; i <= n; i++)
    cin >> h[i];

  int q;
  cin>>q;

  for (int i = 1; i <= n + 45; i++)
    for (int j = 0; j <= 45; j++)
      a[i][j] = 1;
  
  while (q--){
    int tp;
    cin>>tp;
    if (tp == 1){ 
      int x,d,w;
      cin>>x>>d>>w;

      for (int i = 0; i <= d; i++){
        a[x][d - i] = (a[x][d - i] * w) % mod;
        x = par[x];
      }
      continue;
    }

    int x;
    cin>>x;

    int X = x;
    int ans = h[x];
    for (int i = 0; i <= 40; i++){
      ans = ans * a[x][i] % mod;
      x = par[x];
    }

    x = X;
    for (int i = 0; i <= 40; i++){
      ans = ans * a[x][i + 1] % mod;
      x = par[x];
    }
    cout<<ans<<endl;
  }
}

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:52:15: warning: iteration 45 invokes undefined behavior [-Waggressive-loop-optimizations]
   52 |       a[i][j] = 1;
      |       ~~~~~~~~^~~
sprinkler.cpp:51:23: note: within this loop
   51 |     for (int j = 0; j <= 45; j++)
      |                     ~~^~~~~

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