Submission #1189523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189523		mannshah1211	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	694 ms	92228 KiB

sprinkler

/**
 *   author: tourist
 *   created: 21.04.2025 10:06:09
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  long long l;
  cin >> l;
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> pv(n);
  auto Dfs = [&](auto&& self, int v, int pr) -> void {
    pv[v] = pr;
    for (int u : g[v]) {
      if (u != pr) {
        self(self, u, v);
      }
    }
  };
  Dfs(Dfs, 0, -1);
  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }
  vector<vector<int64_t>> lazy(n, vector<int64_t>(41, 1));
  int q;
  cin >> q;
  for (int qq = 0; qq < q; qq++) {
    int op;
    cin >> op;
    if (op == 1) {
      int x, d, w;
      cin >> x >> d >> w;
      int orig_d = d;
      --x;
      for (int j = 0; j <= orig_d; j++) {
        lazy[x][d] *= int64_t(w);
        lazy[x][d] %= l;
        if (d >= 1) {
          lazy[x][d - 1] *= int64_t(w);
          lazy[x][d - 1] %= l;
        }
        if (x == 0) {
          for (int i = 0; i < d - 1; i++) {
            lazy[x][i] *= int64_t(w);
            lazy[x][i] %= l;
          }
        }
        if (x > 0) {
          x = pv[x];
          --d;
        } else {
          break;
        }
      }
    } else {
      int x;
      cin >> x;
      --x;
      int64_t ans = h[x];
      for (int j = 0; j <= 40; j++) {
        ans *= lazy[x][j];
        ans %= l;
        if (pv[x] == -1) {
          break;
        }
        x = pv[x];
      }
      cout << ans << '\n';
    }
  }
  return 0;
}

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