Submission #673747

#	Time	Username	Problem	Language	Result	Execution time	Memory
673747		peijar	Sprinkler (JOI22_sprinkler)	C++17	0 / 100	4103 ms	699828 KiB

sprinkler

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

typedef unsigned long long ull;
struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(-1ULL / b) {}
  ull reduce(ull a) { // a % b + (0 or b)
    return a - (ull)((__uint128_t(m) * a) >> 64) * b;
  }
};

const int MAXN = 2e5;
const int MAXD = 41;

int mod;
FastMod fastmod(1);

struct ProdSegTree {
  vector<int> seg;
  int deb;

  ProdSegTree() {}

  ProdSegTree(int n) {
    deb = 1;
    while (deb < n)
      deb *= 2;
    seg.assign(2 * deb, 1);
  }

  void mult(int pos, int x) {
    pos += deb;
    seg[pos] = fastmod.reduce(x * seg[pos]);
    while (pos > 1) {
      pos /= 2;
      seg[pos] = fastmod.reduce(seg[2 * pos] * seg[2 * pos + 1]);
    }
  }

  int query(int l, int r) { // [l, r)
    l += deb, r += deb;
    int ret = 1;
    while (l < r) {
      if (l % 2)
        ret = fastmod.reduce(ret * seg[l++]);
      if (r % 2)
        ret = fastmod.reduce(ret * seg[--r]);
      l /= 2;
      r /= 2;
    }
    return ret;
  }
};

vector<int> childs[MAXN];
ProdSegTree prodSegTree[MAXN][MAXD];
int nbFils[MAXN];
int par[MAXN], depth[MAXN];
int idPar[MAXN];

void init(int u, int p) {
  for (int &v : childs[u])
    if (v == p) {
      swap(v, childs[u].back());
      childs[u].pop_back();
      break;
    }
  nbFils[u] = childs[u].size();
  for (int d = 0; d < MAXD; ++d)
    prodSegTree[u][d] = ProdSegTree(nbFils[u] + 1);
  for (int i = 0; i < nbFils[u]; ++i) {
    int v = childs[u][i];
    idPar[v] = i;
    par[v] = u;
    depth[v] = depth[u] + 1;
    init(v, u);
  }
}

int query(int u) {
  int facteur = 1;
  for (int d = 0; d < MAXD; ++d)
    facteur =
        fastmod.reduce(facteur * prodSegTree[u][d].query(0, nbFils[u] + 1));

  int v = u;
  for (int i = 1; i < MAXD; ++i) {
    int nxt = par[v];
    for (int d = i; d < MAXD; ++d) {
      facteur =
          fastmod.reduce(facteur * prodSegTree[nxt][d].query(0, idPar[v]));
      facteur = fastmod.reduce(
          facteur * prodSegTree[nxt][d].query(idPar[v] + 1, nbFils[nxt] + 1));
    }
    v = nxt;
    if (v == 0)
      break;
  }
  return facteur;
}

void update(int u, int d, int m) {
  prodSegTree[u][d].mult(nbFils[u], m);
  int v = u;
  for (int i = 1; i <= d; ++i) {
    int nxt = par[v];
    prodSegTree[nxt][d - i].mult(idPar[v], m);
    v = nxt;
    if (!v)
      break;
  }
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommet;
  cin >> nbSommet >> mod;
  fastmod = FastMod(mod);

  for (int i = 1; i < nbSommet; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    childs[u].push_back(v);
    childs[v].push_back(u);
  }

  init(0, 0);
  vector<int> valInit(nbSommet);
  for (int &x : valInit)
    cin >> x;

  int nbRequete;
  cin >> nbRequete;

  for (int i = 0; i < nbRequete; ++i) {
    int t, u;
    cin >> t >> u;
    --u;

    if (t == 2) {
      cout << fastmod.reduce(query(u) * valInit[u]) << '\n';
    } else {
      int d, m;
      cin >> d >> m;
      update(u, d, m);
    }
  }
}

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