Submission #1163214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163214		fryingduc	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	444 ms	62904 KiB

sprinkler

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
int n, q, a[maxn], L;
vector<int> g[maxn];
int f[maxn][44];
int par[maxn], h[maxn];

void pre_dfs(int u, int prev) {
  for (auto v:g[u]) {
    if (v == prev) continue;
    h[v] = h[u] + 1;
    par[v] = u;
    pre_dfs(v, u);
  }
}

void solve() {
  cin >> n >> L;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  pre_dfs(1, 0);
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= 40; ++j) {
      f[i][j] = 1;
    }
  }
  for (int i = 1; i <= n; ++i) {
    cin >> f[i][0];
  }
  cin >> q;
  while (q--) {
    int op; cin >> op;
    if (op == 1) {
      int x, d, w; cin >> x >> d >> w;
      for (int i = d; i >= 0; --i) {
        f[x][i] = 1ll * f[x][i] * w % L;
        if (par[x] and i > 0) {
          f[x][i - 1] = 1ll * f[x][i - 1] * w % L;
        }
        x = (par[x] ? par[x] : x);
      }
    } else {
      int u; cin >> u;
      int cur = 1;
      for (int i = 0; i <= 40; ++i) {
        if (!u) break;
        cur = 1ll * cur * f[u][i] % L;
        u = par[u];
      }
      cout << cur << '\n';
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  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