제출 #785423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785423		christinelynn	Sprinkler (JOI22_sprinkler)	C++17	0 / 100	4046 ms	16440 KiB

sprinkler

#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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17