oj.uz

Submission #673834

# Submission time Handle Problem Language Result Execution time Memory
673834 2022-12-22T08:56:25 Z peijar Sprinkler (JOI22_sprinkler) C++17
12 / 100
 1072 ms 93400 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)
    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
0 / 3.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5024 KB Output is correct
2 Correct 621 ms 83392 KB Output is correct
3 Correct 378 ms 80300 KB Output is correct
4 Correct 624 ms 88744 KB Output is correct
5 Correct 544 ms 83744 KB Output is correct
6 Correct 372 ms 83712 KB Output is correct
7 Correct 343 ms 84180 KB Output is correct
8 Correct 282 ms 84308 KB Output is correct
9 Correct 773 ms 93400 KB Output is correct
10 Correct 382 ms 89420 KB Output is correct
11 Correct 663 ms 85520 KB Output is correct
12 Correct 389 ms 82384 KB Output is correct
13 Correct 272 ms 89432 KB Output is correct
14 Correct 264 ms 92500 KB Output is correct
15 Correct 254 ms 91600 KB Output is correct
16 Correct 265 ms 92184 KB Output is correct
17 Correct 267 ms 92868 KB Output is correct
18 Correct 3 ms 5032 KB Output is correct
19 Incorrect 3 ms 4948 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5024 KB Output is correct
2 Correct 621 ms 83392 KB Output is correct
3 Correct 378 ms 80300 KB Output is correct
4 Correct 624 ms 88744 KB Output is correct
5 Correct 544 ms 83744 KB Output is correct
6 Correct 372 ms 83712 KB Output is correct
7 Correct 343 ms 84180 KB Output is correct
8 Correct 282 ms 84308 KB Output is correct
9 Correct 773 ms 93400 KB Output is correct
10 Correct 382 ms 89420 KB Output is correct
11 Correct 663 ms 85520 KB Output is correct
12 Correct 389 ms 82384 KB Output is correct
13 Correct 272 ms 89432 KB Output is correct
14 Correct 264 ms 92500 KB Output is correct
15 Correct 254 ms 91600 KB Output is correct
16 Correct 265 ms 92184 KB Output is correct
17 Correct 267 ms 92868 KB Output is correct
18 Correct 3 ms 5032 KB Output is correct
19 Incorrect 3 ms 4948 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 843 ms 88968 KB Output is correct
3 Correct 1072 ms 85928 KB Output is correct
4 Correct 754 ms 86664 KB Output is correct
5 Correct 646 ms 80968 KB Output is correct
6 Correct 407 ms 80772 KB Output is correct
7 Correct 358 ms 80872 KB Output is correct
8 Correct 277 ms 81112 KB Output is correct
9 Correct 802 ms 86432 KB Output is correct
10 Correct 1059 ms 87600 KB Output is correct
11 Correct 661 ms 80844 KB Output is correct
12 Correct 806 ms 80276 KB Output is correct
13 Correct 524 ms 81080 KB Output is correct
14 Correct 590 ms 81956 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 5032 KB Output is correct
18 Correct 3 ms 5032 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 805 ms 88676 KB Output is correct
3 Correct 1065 ms 84264 KB Output is correct
4 Correct 800 ms 86492 KB Output is correct
5 Incorrect 647 ms 82600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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