oj.uz

Submission #673835

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5080 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Correct 4 ms 5460 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 4 ms 5432 KB Output is correct
8 Correct 4 ms 5352 KB Output is correct
9 Correct 3 ms 5040 KB Output is correct
10 Correct 3 ms 5036 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 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 5040 KB Output is correct
18 Correct 3 ms 5036 KB Output is correct
19 Correct 4 ms 4948 KB Output is correct
20 Correct 3 ms 5032 KB Output is correct
21 Correct 3 ms 5028 KB Output is correct
22 Correct 3 ms 5080 KB Output is correct
23 Correct 3 ms 4984 KB Output is correct
24 Correct 3 ms 4948 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 3 ms 5032 KB Output is correct
27 Correct 3 ms 5032 KB Output is correct
28 Correct 3 ms 5028 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 675 ms 83552 KB Output is correct
3 Correct 368 ms 80676 KB Output is correct
4 Correct 577 ms 86844 KB Output is correct
5 Correct 516 ms 81864 KB Output is correct
6 Correct 341 ms 81784 KB Output is correct
7 Correct 335 ms 82204 KB Output is correct
8 Correct 314 ms 82360 KB Output is correct
9 Correct 754 ms 91440 KB Output is correct
10 Correct 465 ms 87596 KB Output is correct
11 Correct 651 ms 83592 KB Output is correct
12 Correct 394 ms 80408 KB Output is correct
13 Correct 241 ms 80832 KB Output is correct
14 Correct 243 ms 80672 KB Output is correct
15 Correct 261 ms 80564 KB Output is correct
16 Correct 287 ms 80520 KB Output is correct
17 Correct 266 ms 81212 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 4 ms 5036 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 675 ms 83552 KB Output is correct
3 Correct 368 ms 80676 KB Output is correct
4 Correct 577 ms 86844 KB Output is correct
5 Correct 516 ms 81864 KB Output is correct
6 Correct 341 ms 81784 KB Output is correct
7 Correct 335 ms 82204 KB Output is correct
8 Correct 314 ms 82360 KB Output is correct
9 Correct 754 ms 91440 KB Output is correct
10 Correct 465 ms 87596 KB Output is correct
11 Correct 651 ms 83592 KB Output is correct
12 Correct 394 ms 80408 KB Output is correct
13 Correct 241 ms 80832 KB Output is correct
14 Correct 243 ms 80672 KB Output is correct
15 Correct 261 ms 80564 KB Output is correct
16 Correct 287 ms 80520 KB Output is correct
17 Correct 266 ms 81212 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 4 ms 5036 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 692 ms 91396 KB Output is correct
25 Correct 412 ms 91892 KB Output is correct
26 Correct 588 ms 99404 KB Output is correct
27 Correct 570 ms 91612 KB Output is correct
28 Correct 364 ms 91884 KB Output is correct
29 Correct 352 ms 91496 KB Output is correct
30 Correct 281 ms 92428 KB Output is correct
31 Correct 816 ms 96668 KB Output is correct
32 Correct 437 ms 99180 KB Output is correct
33 Correct 704 ms 91464 KB Output is correct
34 Correct 462 ms 91948 KB Output is correct
35 Correct 3 ms 4948 KB Output is correct
36 Correct 3 ms 5032 KB Output is correct
37 Correct 3 ms 4984 KB Output is correct
38 Correct 3 ms 5032 KB Output is correct
39 Correct 4 ms 4948 KB Output is correct
40 Correct 3 ms 5032 KB Output is correct
41 Correct 3 ms 4948 KB Output is correct
42 Correct 3 ms 5076 KB Output is correct
43 Correct 4 ms 4948 KB Output is correct
44 Correct 3 ms 4948 KB Output is correct
45 Correct 3 ms 5032 KB Output is correct
46 Correct 3 ms 4948 KB Output is correct
47 Correct 3 ms 4948 KB Output is correct
48 Correct 3 ms 4948 KB Output is correct
49 Correct 3 ms 5032 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 865 ms 89176 KB Output is correct
3 Correct 1158 ms 86360 KB Output is correct
4 Correct 751 ms 87120 KB Output is correct
5 Correct 652 ms 80952 KB Output is correct
6 Correct 426 ms 80760 KB Output is correct
7 Correct 354 ms 80880 KB Output is correct
8 Correct 295 ms 81044 KB Output is correct
9 Correct 834 ms 86352 KB Output is correct
10 Correct 1087 ms 87472 KB Output is correct
11 Correct 715 ms 81112 KB Output is correct
12 Correct 889 ms 80336 KB Output is correct
13 Correct 535 ms 81140 KB Output is correct
14 Correct 587 ms 81936 KB Output is correct
15 Correct 4 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 3 ms 5032 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 875 ms 88828 KB Output is correct
3 Correct 1136 ms 84572 KB Output is correct
4 Correct 772 ms 86836 KB Output is correct
5 Correct 690 ms 82508 KB Output is correct
6 Correct 428 ms 90456 KB Output is correct
7 Correct 397 ms 90196 KB Output is correct
8 Correct 302 ms 90248 KB Output is correct
9 Correct 953 ms 98552 KB Output is correct
10 Correct 1118 ms 97432 KB Output is correct
11 Correct 703 ms 91096 KB Output is correct
12 Correct 797 ms 89524 KB Output is correct
13 Correct 541 ms 90268 KB Output is correct
14 Correct 562 ms 91156 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5080 KB Output is correct
3 Correct 3 ms 5032 KB Output is correct
4 Correct 4 ms 5460 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 4 ms 5432 KB Output is correct
8 Correct 4 ms 5352 KB Output is correct
9 Correct 3 ms 5040 KB Output is correct
10 Correct 3 ms 5036 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 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 5040 KB Output is correct
18 Correct 3 ms 5036 KB Output is correct
19 Correct 4 ms 4948 KB Output is correct
20 Correct 3 ms 5032 KB Output is correct
21 Correct 3 ms 5028 KB Output is correct
22 Correct 3 ms 5080 KB Output is correct
23 Correct 3 ms 4984 KB Output is correct
24 Correct 3 ms 4948 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 3 ms 5032 KB Output is correct
27 Correct 3 ms 5032 KB Output is correct
28 Correct 3 ms 5028 KB Output is correct
29 Correct 3 ms 4948 KB Output is correct
30 Correct 675 ms 83552 KB Output is correct
31 Correct 368 ms 80676 KB Output is correct
32 Correct 577 ms 86844 KB Output is correct
33 Correct 516 ms 81864 KB Output is correct
34 Correct 341 ms 81784 KB Output is correct
35 Correct 335 ms 82204 KB Output is correct
36 Correct 314 ms 82360 KB Output is correct
37 Correct 754 ms 91440 KB Output is correct
38 Correct 465 ms 87596 KB Output is correct
39 Correct 651 ms 83592 KB Output is correct
40 Correct 394 ms 80408 KB Output is correct
41 Correct 241 ms 80832 KB Output is correct
42 Correct 243 ms 80672 KB Output is correct
43 Correct 261 ms 80564 KB Output is correct
44 Correct 287 ms 80520 KB Output is correct
45 Correct 266 ms 81212 KB Output is correct
46 Correct 3 ms 4948 KB Output is correct
47 Correct 3 ms 4948 KB Output is correct
48 Correct 4 ms 5036 KB Output is correct
49 Correct 3 ms 4948 KB Output is correct
50 Correct 3 ms 4948 KB Output is correct
51 Correct 3 ms 4948 KB Output is correct
52 Correct 692 ms 91396 KB Output is correct
53 Correct 412 ms 91892 KB Output is correct
54 Correct 588 ms 99404 KB Output is correct
55 Correct 570 ms 91612 KB Output is correct
56 Correct 364 ms 91884 KB Output is correct
57 Correct 352 ms 91496 KB Output is correct
58 Correct 281 ms 92428 KB Output is correct
59 Correct 816 ms 96668 KB Output is correct
60 Correct 437 ms 99180 KB Output is correct
61 Correct 704 ms 91464 KB Output is correct
62 Correct 462 ms 91948 KB Output is correct
63 Correct 3 ms 4948 KB Output is correct
64 Correct 3 ms 5032 KB Output is correct
65 Correct 3 ms 4984 KB Output is correct
66 Correct 3 ms 5032 KB Output is correct
67 Correct 4 ms 4948 KB Output is correct
68 Correct 3 ms 5032 KB Output is correct
69 Correct 3 ms 4948 KB Output is correct
70 Correct 3 ms 5076 KB Output is correct
71 Correct 4 ms 4948 KB Output is correct
72 Correct 3 ms 4948 KB Output is correct
73 Correct 3 ms 5032 KB Output is correct
74 Correct 3 ms 4948 KB Output is correct
75 Correct 3 ms 4948 KB Output is correct
76 Correct 3 ms 4948 KB Output is correct
77 Correct 3 ms 5032 KB Output is correct
78 Correct 3 ms 5076 KB Output is correct
79 Correct 865 ms 89176 KB Output is correct
80 Correct 1158 ms 86360 KB Output is correct
81 Correct 751 ms 87120 KB Output is correct
82 Correct 652 ms 80952 KB Output is correct
83 Correct 426 ms 80760 KB Output is correct
84 Correct 354 ms 80880 KB Output is correct
85 Correct 295 ms 81044 KB Output is correct
86 Correct 834 ms 86352 KB Output is correct
87 Correct 1087 ms 87472 KB Output is correct
88 Correct 715 ms 81112 KB Output is correct
89 Correct 889 ms 80336 KB Output is correct
90 Correct 535 ms 81140 KB Output is correct
91 Correct 587 ms 81936 KB Output is correct
92 Correct 4 ms 4948 KB Output is correct
93 Correct 4 ms 4948 KB Output is correct
94 Correct 3 ms 5032 KB Output is correct
95 Correct 3 ms 4948 KB Output is correct
96 Correct 3 ms 4948 KB Output is correct
97 Correct 3 ms 4948 KB Output is correct
98 Correct 875 ms 88828 KB Output is correct
99 Correct 1136 ms 84572 KB Output is correct
100 Correct 772 ms 86836 KB Output is correct
101 Correct 690 ms 82508 KB Output is correct
102 Correct 428 ms 90456 KB Output is correct
103 Correct 397 ms 90196 KB Output is correct
104 Correct 302 ms 90248 KB Output is correct
105 Correct 953 ms 98552 KB Output is correct
106 Correct 1118 ms 97432 KB Output is correct
107 Correct 703 ms 91096 KB Output is correct
108 Correct 797 ms 89524 KB Output is correct
109 Correct 541 ms 90268 KB Output is correct
110 Correct 562 ms 91156 KB Output is correct
111 Correct 3 ms 4948 KB Output is correct
112 Correct 2 ms 4948 KB Output is correct
113 Correct 3 ms 4948 KB Output is correct
114 Correct 4 ms 4948 KB Output is correct
115 Correct 3 ms 4948 KB Output is correct
116 Correct 710 ms 89508 KB Output is correct
117 Correct 874 ms 92000 KB Output is correct
118 Correct 812 ms 99140 KB Output is correct
119 Correct 710 ms 91720 KB Output is correct
120 Correct 398 ms 91280 KB Output is correct
121 Correct 394 ms 92188 KB Output is correct
122 Correct 313 ms 92224 KB Output is correct
123 Correct 865 ms 97688 KB Output is correct
124 Correct 1111 ms 96348 KB Output is correct
125 Correct 664 ms 90700 KB Output is correct
126 Correct 892 ms 91968 KB Output is correct
127 Correct 912 ms 92432 KB Output is correct
128 Correct 581 ms 93100 KB Output is correct
129 Correct 581 ms 94072 KB Output is correct