제출 #785471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785471		andecaandeci	Sprinkler (JOI22_sprinkler)	C++17	3 / 100	4082 ms	17928 KiB

sprinkler

#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() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  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 / 3
• Subtask 2: 0 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17