제출 #848031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
848031		NeroZein	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	576 ms	60752 KiB

sprinkler

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

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

int dp[N][D]; 
int parent[N]; 
vector<int> g[N]; 

void dfs(int v, int p) {
  parent[v] = p;
  for (int u : g[v]) if (u != p) dfs(u, v);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, l;
  cin >> n >> l;
  auto mul = [&](int x, int y) {
    return (int) ((long long) x * y % l); 
  };
  for(int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 0);
  for (int i = 1; i <= n; ++i) {
    fill(dp[i], dp[i] + D, 1); 
  }
  for (int i = 1; i <= n; ++i) {
    cin >> dp[i][0];
  }
  int q;
  cin >> q;
  while (q--) {
    int t, v;
    cin >> t >> v;
    if (t == 1) {
      int d, w;
      cin >> d >> w;
      while (d > 0 && v != 1) {
        dp[v][d] = mul(dp[v][d], w);//if the distance is d - 1, to parent will be d + 1 
        dp[v][d - 1] = mul(dp[v][d - 1], w);
        d--;
        v = parent[v];
      }
      for (int i = 0; i <= d; ++i) {
        dp[v][i] = mul(dp[v][i], w); 
      }
    } else {
      int ans = 1;
      for (int i = 0; i < D && v; ++i, v = parent[v]) {
        ans = mul(ans, dp[v][i]);
      }
      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