oj.uz

Submission #785464

# Submission time Handle Problem Language Result Execution time Memory
785464 2023-07-17T09:22:43 Z devariaota Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 17940 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

int dis[200005], h[200005];
vector<int> adjl[200005];
int n, l, a, b;

int kali(int a, int b) {
  return ((a%l)*(b%l))%l;
}

void bfs(int start, int d, int w) {
  queue<int> q;
  memset(dis, -1, sizeof(dis));
  q.push(start);
  dis[start] = 0;
  h[start] = kali(h[start], w);
  while (!q.empty()) {
    int cur = q.front();
    q.pop();

    for (auto i: adjl[cur]) {
      if (dis[i] == -1) {
        dis[i] = dis[cur]+1;
        if (dis[i] <= d) {
          
          h[i] = kali(h[i], w);
          if (dis[i] < d) {
            q.push(i);
          }
        }
      }
    }
  }
}

signed main() {
  cin >> n >> l;
  for (int i = 1; i < n; i++) {
    cin >> a >> b;
    adjl[a].push_back(b);
    adjl[b].push_back(a);
  }
  for (int i = 1; i <= n; i++) cin >> h[i];

  int q, t, x, d, w;
  cin >> q;
  while (q--) {
    cin >> t;
    if (t == 1) {
      cin >> x >> d >> w;
      if (d == 0) h[x] = kali(h[x], w);
      else if (d == 1) {
        h[x] = kali(h[x], w);
        for (auto i: adjl[x]) h[i] = kali(h[i], w);
      }
      else bfs(x, d, w);
    }
    else if (t == 2) {
      cin >> x;
      cout << h[x]%l << endl;
    }
  }

}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct
4 Correct 19 ms 6616 KB Output is correct
5 Correct 19 ms 6612 KB Output is correct
6 Correct 24 ms 6616 KB Output is correct
7 Correct 27 ms 6624 KB Output is correct
8 Correct 26 ms 6628 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 8 ms 6560 KB Output is correct
15 Correct 9 ms 6572 KB Output is correct
16 Correct 8 ms 6484 KB Output is correct
17 Correct 8 ms 6484 KB Output is correct
18 Correct 8 ms 6572 KB Output is correct
19 Correct 8 ms 6484 KB Output is correct
20 Correct 10 ms 6484 KB Output is correct
21 Correct 9 ms 6544 KB Output is correct
22 Correct 8 ms 6484 KB Output is correct
23 Correct 8 ms 6484 KB Output is correct
24 Correct 11 ms 6484 KB Output is correct
25 Correct 8 ms 6572 KB Output is correct
26 Correct 8 ms 6572 KB Output is correct
27 Correct 8 ms 6484 KB Output is correct
28 Correct 9 ms 6580 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 762 ms 17396 KB Output is correct
3 Correct 582 ms 14152 KB Output is correct
4 Correct 784 ms 14648 KB Output is correct
5 Correct 698 ms 15752 KB Output is correct
6 Correct 666 ms 15852 KB Output is correct
7 Correct 713 ms 16168 KB Output is correct
8 Correct 643 ms 16352 KB Output is correct
9 Correct 758 ms 16348 KB Output is correct
10 Correct 570 ms 13276 KB Output is correct
11 Correct 877 ms 17380 KB Output is correct
12 Correct 572 ms 14216 KB Output is correct
13 Execution timed out 4046 ms 14192 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 762 ms 17396 KB Output is correct
3 Correct 582 ms 14152 KB Output is correct
4 Correct 784 ms 14648 KB Output is correct
5 Correct 698 ms 15752 KB Output is correct
6 Correct 666 ms 15852 KB Output is correct
7 Correct 713 ms 16168 KB Output is correct
8 Correct 643 ms 16352 KB Output is correct
9 Correct 758 ms 16348 KB Output is correct
10 Correct 570 ms 13276 KB Output is correct
11 Correct 877 ms 17380 KB Output is correct
12 Correct 572 ms 14216 KB Output is correct
13 Execution timed out 4046 ms 14192 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 2278 ms 15196 KB Output is correct
3 Execution timed out 4038 ms 14396 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 2333 ms 17940 KB Output is correct
3 Execution timed out 4078 ms 14432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 6484 KB Output is correct
4 Correct 19 ms 6616 KB Output is correct
5 Correct 19 ms 6612 KB Output is correct
6 Correct 24 ms 6616 KB Output is correct
7 Correct 27 ms 6624 KB Output is correct
8 Correct 26 ms 6628 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 8 ms 6560 KB Output is correct
15 Correct 9 ms 6572 KB Output is correct
16 Correct 8 ms 6484 KB Output is correct
17 Correct 8 ms 6484 KB Output is correct
18 Correct 8 ms 6572 KB Output is correct
19 Correct 8 ms 6484 KB Output is correct
20 Correct 10 ms 6484 KB Output is correct
21 Correct 9 ms 6544 KB Output is correct
22 Correct 8 ms 6484 KB Output is correct
23 Correct 8 ms 6484 KB Output is correct
24 Correct 11 ms 6484 KB Output is correct
25 Correct 8 ms 6572 KB Output is correct
26 Correct 8 ms 6572 KB Output is correct
27 Correct 8 ms 6484 KB Output is correct
28 Correct 9 ms 6580 KB Output is correct
29 Correct 3 ms 4948 KB Output is correct
30 Correct 762 ms 17396 KB Output is correct
31 Correct 582 ms 14152 KB Output is correct
32 Correct 784 ms 14648 KB Output is correct
33 Correct 698 ms 15752 KB Output is correct
34 Correct 666 ms 15852 KB Output is correct
35 Correct 713 ms 16168 KB Output is correct
36 Correct 643 ms 16352 KB Output is correct
37 Correct 758 ms 16348 KB Output is correct
38 Correct 570 ms 13276 KB Output is correct
39 Correct 877 ms 17380 KB Output is correct
40 Correct 572 ms 14216 KB Output is correct
41 Execution timed out 4046 ms 14192 KB Time limit exceeded
42 Halted 0 ms 0 KB -