Submission #1189468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189468		tch1cherin	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	634 ms	63652 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  constexpr int MAX_D = 45;
  int N, L;
  cin >> N >> L;
  vector<vector<int>> graph(N + MAX_D);
  for (int i = 0; i < N - 1; i++) {
    int A, B;
    cin >> A >> B;
    --A, --B;
    graph[A].push_back(B);
    graph[B].push_back(A);
  }
  for (int i = 0; i < MAX_D; i++) {
    graph[N + i].push_back(N + i - 1);
    graph[N + i - 1].push_back(N + i);
  }
  vector<int> parent(N + MAX_D, -1);
  auto DFS = [&](auto&& self, int u) -> void {
    for (int v : graph[u]) {
      if (v != parent[u]) {
        parent[v] = u;
        self(self, v);
      }
    }
  };
  DFS(DFS, N + MAX_D - 1);
  vector<vector<int>> tag(N + MAX_D, vector<int>(MAX_D, 1));
  for (int i = 0; i < N; i++) {
    cin >> tag[i][0];
  }
  int Q;
  cin >> Q;
  while (Q--) {
    int T, X;
    cin >> T >> X;
    --X;
    if (T == 1) {
      int D, W;
      cin >> D >> W;
      while (D > 0) {
        tag[X][D] = 1LL * tag[X][D] * W % L;
        --D;
        tag[X][D] = 1LL * tag[X][D] * W % L;
        X = parent[X];
      }
      tag[X][0] = 1LL * tag[X][0] * W % L;
    } else {
      int result = 1;      
      for (int i = 0; i < MAX_D; i++) {
        result = 1LL * result * tag[X][i] % L;
        X = parent[X];
      }
      cout << result << "\n";
    }
  }
}

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