oj.uz

Submission #673831

# Submission time Handle Problem Language Result Execution time Memory
673831 2022-12-22T08:44:40 Z peijar Sprinkler (JOI22_sprinkler) C++17
12 / 100
 1133 ms 96328 KB 
#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);

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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 3 ms 5460 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 5 ms 5424 KB Output is correct
7 Incorrect 4 ms 5428 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5032 KB Output is correct
2 Correct 621 ms 85028 KB Output is correct
3 Incorrect 412 ms 81744 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5032 KB Output is correct
2 Correct 621 ms 85028 KB Output is correct
3 Incorrect 412 ms 81744 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 817 ms 90132 KB Output is correct
3 Correct 1133 ms 87228 KB Output is correct
4 Correct 750 ms 88060 KB Output is correct
5 Correct 672 ms 83304 KB Output is correct
6 Correct 398 ms 88780 KB Output is correct
7 Correct 417 ms 89040 KB Output is correct
8 Correct 267 ms 89276 KB Output is correct
9 Correct 828 ms 93800 KB Output is correct
10 Correct 1110 ms 96328 KB Output is correct
11 Correct 670 ms 88356 KB Output is correct
12 Correct 886 ms 89192 KB Output is correct
13 Correct 531 ms 90212 KB Output is correct
14 Correct 577 ms 91008 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 5028 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 855 ms 89888 KB Output is correct
3 Correct 1089 ms 85512 KB Output is correct
4 Correct 771 ms 87852 KB Output is correct
5 Incorrect 663 ms 84444 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5028 KB Output is correct
4 Correct 3 ms 5460 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 5 ms 5424 KB Output is correct
7 Incorrect 4 ms 5428 KB Output isn't correct
8 Halted 0 ms 0 KB -