Submission #980477

#	Time	Username	Problem	Language	Result	Execution time	Memory
980477		abczz	Sprinkler (JOI22_sprinkler)	C++14	41 / 100	4030 ms	421352 KiB

sprinkler

#include <iostream>
#include <vector>
#define ll long long

using namespace std;

ll n, q, t, M, a, b, c, f, cnt, H[200000], edgeid[200000], P[200000], X[200000], dp[200000][41];
struct BIT{
  vector <ll> bit{vector <ll> (42, 1)};
  void mult(ll u, ll w) {
    u = 42-u;
    while (u < 42) {
      bit[u] = bit[u] * w % M;
      u += u & -u;
    }
  }
  ll query(ll u) {
    u = 42-u;
    ll res = 1;
    while (u) {
      res *= bit[u];
      res %= M;
      u -= u & -u;
    }
    return res;
  }
};
struct SegTree{
  vector <BIT> st;
  ll stsz = 0;
  void init() {
    st.resize(4*stsz);
  }
  void update(ll id, ll l, ll r, ll q, ll u, ll w) {
    st[id].mult(u, w);
    if (l == r) return;
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q, u, w);
    else update(id*2+1, mid+1, r, q, u, w);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr, ll u) {
    if (qr < l || r < ql || ql > qr) return 1;
    else if (ql <= l && r <= qr) return st[id].query(u);
    ll mid = (l+r)/2;
    return query(id*2, l, mid, ql, qr, u) * query(id*2+1, mid+1, r, ql, qr, u) % M;
  }
}ST[200000];
vector <ll> adj[200000];
BIT G[200000];

void dfs(ll u, ll p) {
  for (auto v : adj[u]) {
    if (v != p) {
      X[v] = ST[u].stsz++;
      edgeid[v] = cnt++;
      dfs(v, u);
      P[v] = u;
    }
  }
  ST[u].init();
}
int main() {
  cin >> n >> M;
  for (int i=0; i<n-1; ++i) {
    cin >> a >> b;
    --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for (int i=0; i<n; ++i) {
    cin >> H[i];
  }
  dfs(0, -1);
  P[0] = -1;
  cin >> q;
  while (q--) {
    cin >> t;
    if (t == 1) {
      cin >> a >> b >> c;
      --a;
      G[a].mult(b+1, c);
      for (int i=b-1; i>=0 && P[a] != -1; --i) {
        ST[P[a]].update(1, 0, ST[P[a]].stsz-1, X[a], i+1, c);
        a = P[a];
      }
    }
    else {
      cin >> a;
      --a;
      f = H[a] * G[a].query(1) % M;
      f = f * ST[a].query(1, 0, ST[a].stsz-1, 0, ST[a].stsz-1, 1) % M;
      for (int i=1; i<=40 && P[a] != -1; ++i) {
        f = f * G[P[a]].query(i+1) % M;
        f = f * ST[P[a]].query(1, 0, ST[P[a]].stsz-1, 0, X[a]-1, i+1) % M * ST[P[a]].query(1, 0, ST[P[a]].stsz-1, X[a]+1, ST[P[a]].stsz-1, i+1) % M;
        a = P[a];
      }
      cout << f << '\n';
    }
  }
}

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