Submission #1037499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037499		juicy	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	461 ms	68692 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;

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

const int N = 2e5 + 5, D = 41;

int n, q, L;
int pr[N], dp[N][D], dep[N];
vector<int> g[N];

void dfs(int u) {
  for (int v : g[u]) {
    if (v != pr[u]) {
      pr[v] = u;
      dep[v] = dep[u] + 1;
      dfs(v);
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  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);
  }
  pr[1] = 1;
  dfs(1);
  for (int i = 1; i <= n; ++i) {
    cin >> dp[i][0];
    fill(dp[i] + 1, dp[i] + D, 1);
  }
  cin >> q;
  while (q--) {
    int type; cin >> type;
    if (type == 1) {
      int u, d, w; cin >> u >> d >> w;
      for (int i = 0; i <= d; ++i, u = pr[u]) {
        dp[u][d - i] = (long long) dp[u][d - i] * w % L;
        if (u != pr[u] && d - i) {
          dp[u][d - i - 1] = (long long) dp[u][d - i - 1] * w % L; 
        }
      }
    } else {
      int u; cin >> u;
      int res = 1, d = dep[u] + 1;
      for (int i = 0; i < min(D, d); ++i, u = pr[u]) {
        res = (long long) res * dp[u][i] % L;
      }
      cout << res << "\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