oj.uz

Submission #1024534

# Submission time Handle Problem Language Result Execution time Memory
1024534 2024-07-16T07:03:27 Z 우민규(#10936) Sprinkler (JOI22_sprinkler) C++17
100 / 100
 680 ms 72052 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

const int MAX_D = 41;

int n, q, l;
void m(int& a, int b) { a = (int64_t)a * (int64_t)b % l; }
vector<vector<int>> adj;
vector<int> par;
vector<vector<int>> mul;

void dfs(int node) {
  for (auto v : adj[node])
    if (v != par[node]) par[v] = node, dfs(v);
}

void solve() {
  cin >> n >> l;
  adj.assign(n, {});
  par.assign(n, -1);
  mul.assign(n, vector<int>(MAX_D, 1));
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u - 1].push_back(v - 1);
    adj[v - 1].push_back(u - 1);
  }
  for (int i = 0; i < n; ++i) cin >> mul[i][0];
  dfs(0);

  cin >> q;
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int x, d, w;
      cin >> x >> d >> w;
      x -= 1;
      while (d >= 0) {
        m(mul[x][d], w);
        if (x != 0) {
          m(mul[x][d - 1], w);
          x = par[x];
        }
        d -= 1;
      }
    } else {
      int x, d = 0;
      cin >> x;
      x -= 1;
      int val = 1;
      while (d < MAX_D) {
        m(val, mul[x][d]);
        if (x == 0) break;
        x = par[x];
        d += 1;
      }
      cout << val << "\n";
    }
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t = 1;

  while (t--) {
    solve();
  }
  return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 464 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 392 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 434 ms 63200 KB Output is correct
3 Correct 259 ms 63568 KB Output is correct
4 Correct 368 ms 69200 KB Output is correct
5 Correct 343 ms 63436 KB Output is correct
6 Correct 233 ms 62828 KB Output is correct
7 Correct 243 ms 63568 KB Output is correct
8 Correct 189 ms 64200 KB Output is correct
9 Correct 475 ms 72052 KB Output is correct
10 Correct 258 ms 71760 KB Output is correct
11 Correct 437 ms 63060 KB Output is correct
12 Correct 239 ms 63568 KB Output is correct
13 Correct 185 ms 63940 KB Output is correct
14 Correct 166 ms 64452 KB Output is correct
15 Correct 174 ms 63824 KB Output is correct
16 Correct 183 ms 64040 KB Output is correct
17 Correct 185 ms 64592 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 400 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 434 ms 63200 KB Output is correct
3 Correct 259 ms 63568 KB Output is correct
4 Correct 368 ms 69200 KB Output is correct
5 Correct 343 ms 63436 KB Output is correct
6 Correct 233 ms 62828 KB Output is correct
7 Correct 243 ms 63568 KB Output is correct
8 Correct 189 ms 64200 KB Output is correct
9 Correct 475 ms 72052 KB Output is correct
10 Correct 258 ms 71760 KB Output is correct
11 Correct 437 ms 63060 KB Output is correct
12 Correct 239 ms 63568 KB Output is correct
13 Correct 185 ms 63940 KB Output is correct
14 Correct 166 ms 64452 KB Output is correct
15 Correct 174 ms 63824 KB Output is correct
16 Correct 183 ms 64040 KB Output is correct
17 Correct 185 ms 64592 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 400 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 439 ms 63120 KB Output is correct
25 Correct 248 ms 63568 KB Output is correct
26 Correct 380 ms 72020 KB Output is correct
27 Correct 335 ms 63316 KB Output is correct
28 Correct 235 ms 63452 KB Output is correct
29 Correct 205 ms 53328 KB Output is correct
30 Correct 209 ms 62152 KB Output is correct
31 Correct 467 ms 68432 KB Output is correct
32 Correct 288 ms 69716 KB Output is correct
33 Correct 400 ms 57976 KB Output is correct
34 Correct 256 ms 52048 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 604 KB Output is correct
48 Correct 1 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 510 ms 61252 KB Output is correct
3 Correct 665 ms 67452 KB Output is correct
4 Correct 476 ms 67604 KB Output is correct
5 Correct 405 ms 60500 KB Output is correct
6 Correct 265 ms 60420 KB Output is correct
7 Correct 233 ms 60496 KB Output is correct
8 Correct 197 ms 61128 KB Output is correct
9 Correct 500 ms 66388 KB Output is correct
10 Correct 644 ms 68880 KB Output is correct
11 Correct 467 ms 59984 KB Output is correct
12 Correct 619 ms 60788 KB Output is correct
13 Correct 366 ms 61892 KB Output is correct
14 Correct 432 ms 62288 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 531 ms 64884 KB Output is correct
3 Correct 664 ms 63672 KB Output is correct
4 Correct 482 ms 67264 KB Output is correct
5 Correct 415 ms 62036 KB Output is correct
6 Correct 252 ms 62036 KB Output is correct
7 Correct 227 ms 61776 KB Output is correct
8 Correct 211 ms 62228 KB Output is correct
9 Correct 530 ms 70996 KB Output is correct
10 Correct 657 ms 69712 KB Output is correct
11 Correct 447 ms 62744 KB Output is correct
12 Correct 553 ms 61140 KB Output is correct
13 Correct 355 ms 62200 KB Output is correct
14 Correct 414 ms 62448 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 464 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 392 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 434 ms 63200 KB Output is correct
31 Correct 259 ms 63568 KB Output is correct
32 Correct 368 ms 69200 KB Output is correct
33 Correct 343 ms 63436 KB Output is correct
34 Correct 233 ms 62828 KB Output is correct
35 Correct 243 ms 63568 KB Output is correct
36 Correct 189 ms 64200 KB Output is correct
37 Correct 475 ms 72052 KB Output is correct
38 Correct 258 ms 71760 KB Output is correct
39 Correct 437 ms 63060 KB Output is correct
40 Correct 239 ms 63568 KB Output is correct
41 Correct 185 ms 63940 KB Output is correct
42 Correct 166 ms 64452 KB Output is correct
43 Correct 174 ms 63824 KB Output is correct
44 Correct 183 ms 64040 KB Output is correct
45 Correct 185 ms 64592 KB Output is correct
46 Correct 0 ms 344 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 400 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 439 ms 63120 KB Output is correct
53 Correct 248 ms 63568 KB Output is correct
54 Correct 380 ms 72020 KB Output is correct
55 Correct 335 ms 63316 KB Output is correct
56 Correct 235 ms 63452 KB Output is correct
57 Correct 205 ms 53328 KB Output is correct
58 Correct 209 ms 62152 KB Output is correct
59 Correct 467 ms 68432 KB Output is correct
60 Correct 288 ms 69716 KB Output is correct
61 Correct 400 ms 57976 KB Output is correct
62 Correct 256 ms 52048 KB Output is correct
63 Correct 1 ms 348 KB Output is correct
64 Correct 0 ms 348 KB Output is correct
65 Correct 1 ms 348 KB Output is correct
66 Correct 0 ms 348 KB Output is correct
67 Correct 1 ms 348 KB Output is correct
68 Correct 0 ms 348 KB Output is correct
69 Correct 0 ms 348 KB Output is correct
70 Correct 0 ms 348 KB Output is correct
71 Correct 0 ms 348 KB Output is correct
72 Correct 0 ms 348 KB Output is correct
73 Correct 0 ms 348 KB Output is correct
74 Correct 0 ms 348 KB Output is correct
75 Correct 0 ms 604 KB Output is correct
76 Correct 1 ms 348 KB Output is correct
77 Correct 0 ms 348 KB Output is correct
78 Correct 0 ms 348 KB Output is correct
79 Correct 510 ms 61252 KB Output is correct
80 Correct 665 ms 67452 KB Output is correct
81 Correct 476 ms 67604 KB Output is correct
82 Correct 405 ms 60500 KB Output is correct
83 Correct 265 ms 60420 KB Output is correct
84 Correct 233 ms 60496 KB Output is correct
85 Correct 197 ms 61128 KB Output is correct
86 Correct 500 ms 66388 KB Output is correct
87 Correct 644 ms 68880 KB Output is correct
88 Correct 467 ms 59984 KB Output is correct
89 Correct 619 ms 60788 KB Output is correct
90 Correct 366 ms 61892 KB Output is correct
91 Correct 432 ms 62288 KB Output is correct
92 Correct 0 ms 348 KB Output is correct
93 Correct 0 ms 348 KB Output is correct
94 Correct 0 ms 348 KB Output is correct
95 Correct 0 ms 348 KB Output is correct
96 Correct 0 ms 348 KB Output is correct
97 Correct 0 ms 348 KB Output is correct
98 Correct 531 ms 64884 KB Output is correct
99 Correct 664 ms 63672 KB Output is correct
100 Correct 482 ms 67264 KB Output is correct
101 Correct 415 ms 62036 KB Output is correct
102 Correct 252 ms 62036 KB Output is correct
103 Correct 227 ms 61776 KB Output is correct
104 Correct 211 ms 62228 KB Output is correct
105 Correct 530 ms 70996 KB Output is correct
106 Correct 657 ms 69712 KB Output is correct
107 Correct 447 ms 62744 KB Output is correct
108 Correct 553 ms 61140 KB Output is correct
109 Correct 355 ms 62200 KB Output is correct
110 Correct 414 ms 62448 KB Output is correct
111 Correct 1 ms 344 KB Output is correct
112 Correct 1 ms 348 KB Output is correct
113 Correct 0 ms 348 KB Output is correct
114 Correct 1 ms 348 KB Output is correct
115 Correct 0 ms 348 KB Output is correct
116 Correct 479 ms 61068 KB Output is correct
117 Correct 552 ms 63572 KB Output is correct
118 Correct 497 ms 71880 KB Output is correct
119 Correct 427 ms 63292 KB Output is correct
120 Correct 271 ms 63056 KB Output is correct
121 Correct 276 ms 63712 KB Output is correct
122 Correct 209 ms 64108 KB Output is correct
123 Correct 531 ms 70328 KB Output is correct
124 Correct 680 ms 68940 KB Output is correct
125 Correct 460 ms 62288 KB Output is correct
126 Correct 542 ms 63692 KB Output is correct
127 Correct 551 ms 64056 KB Output is correct
128 Correct 375 ms 64788 KB Output is correct
129 Correct 416 ms 65180 KB Output is correct