Submission #993060

#	Time	Username	Problem	Language	Result	Execution time	Memory
993060		abczz	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	563 ms	95828 KiB

sprinkler

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

using namespace std;

vector <ll> adj[200000];
bool up;
ll n, M, q, t, a, b, c, p, f, H[200000], P[200000], par[200000][41];

void dfs(ll u, ll p) {
  for (auto v : adj[u]) {
    if (p != v) {
      P[v] = u;
      dfs(v, u);
    }
  }
}
int main() { 
  cin.tie(0);
  ios::sync_with_stdio(0);
  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];
    for (int j=0; j<=40; ++j) par[i][j] = 1;
  }
  dfs(0, -1);
  P[0] = -1;
  cin >> q;
  while (q--) {
    cin >> t;
    if (t == 1) {
      cin >> a >> b >> c;
      --a;
      up = 0;
      for (int i=b; i>=0; --i) {
        par[a][i] *= c;
        par[a][i] %= M;
        up ^= 1;
        if (!up) {
          if (P[a] != -1) {
            a = P[a];
            ++i;
            up = 0;
          }
        }
      }
    }
    else {
      cin >> a;
      --a;
      f = H[a];
      for (int i=0; i<=40; ++i) {
        f *= par[a][i];
        f %= M;
        a = P[a];
        if (a == -1) break;
      }
      cout << f << '\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