oj.uz

Submission #785423

# Submission time Handle Problem Language Result Execution time Memory
785423 2023-07-17T09:04:05 Z christinelynn Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 16440 KB 
#include <bits/stdc++.h>
using namespace std;

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

// void dijkstra(int s) {
//   memset(dis, -1, sizeof(dis));
//   priority_queue<pair<int, int>> s;

//   s.push({0, s});
//   dis[s] = 0;

//   while(!priority_queue.empty()) {
//     int u = s.top().second;
//     int curDist = s.top().first;
    
//     if (!vis[u]) {
//       for (auto i: adjl[u]) {
//         if ()
//       }
//     }
    
//   }

// }
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) {
          q.push(i);
          h[i] = kali(h[i], w);
        }
      }
    }
  }
}

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;
      bfs(x, d, w);
    }
    else if (t == 2) {
      cin >> x;
      cout << h[x]%l << endl;
    }
  }

}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Incorrect 11 ms 5716 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Incorrect 1216 ms 16440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Incorrect 1216 ms 16440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 1537 ms 13640 KB Output is correct
3 Execution timed out 4046 ms 12832 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 5716 KB Output is correct
2 Correct 1613 ms 16292 KB Output is correct
3 Execution timed out 4030 ms 13072 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 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Incorrect 11 ms 5716 KB Output isn't correct
5 Halted 0 ms 0 KB -