Submission #673835

#	Time	Username	Problem	Language	Result	Execution time	Memory
673835		peijar	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1158 ms	99404 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)
    ull x = a - (ull)((__uint128_t(m) * a) >> 64) * b;
    if (x >= b)
      x -= b;
    return x;
  }
};

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

int mod;
FastMod fastmod(1);

vector<int> childs[MAXN];
int par[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;
    }
  for (int v : childs[u]) {
    par[v] = u;
    init(v, u);
  }
}

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;

  vector<array<int, MAXD>> dp(nbSommet);
  for (auto &arr : dp)
    arr.fill(1);

  int nbRequete;
  cin >> nbRequete;

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

    if (t == 2) {
      int sol = valInit[u];
      for (int d = 0; d < MAXD; ++d) {
        sol = fastmod.reduce(sol * dp[u][d]);
        if (!u)
          break;
        u = par[u];
      }
      cout << sol << '\n';
    } else {
      int d, m;
      cin >> d >> m;
      for (int j = 0; j <= d; ++j) {
        dp[u][d - j] = fastmod.reduce(dp[u][d - j] * m);
        if (u and d - j > 0)
          dp[u][d - j - 1] = fastmod.reduce(dp[u][d - j - 1] * m);
        u = par[u];
      }
    }
  }
}

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