Submission #785509

#	Time	Username	Problem	Language	Result	Execution time	Memory
785509		andecaandeci	Sprinkler (JOI22_sprinkler)	C++17	3 / 100	4059 ms	15444 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;
}

int pangkat(int a, int n) {
  if (n == 0) return 1;
  if (n == 1) return a%l;

  int temp = pangkat(a, n/2);
  temp = kali(temp, temp);
  if (n%2 == 1) return kali(temp, a);
  return temp;
}

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);
          }
        }
      }
    }
  }
}

map<vector<int>, int> freq;

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;
      freq[{x, d, w}]++;
    }
    else if (t == 2) {
      for (auto i: freq) {
        if (i.second > 0) {
          // cout << i.first[0] << " " << i.first[1] << " " << i.first[2] << " " << i.second << endl;
          if (i.first[1] == 0) h[i.first[0]] = kali(h[i.first[0]], pangkat(i.first[2], i.second));
          else if (i.first[1] == 1) {
            h[i.first[0]] = kali(h[i.first[0]], pangkat(i.first[2], i.second));
            for (auto j: adjl[i.first[0]]) h[j] = kali(h[j], pangkat(i.first[2], i.second));
          }
          else bfs(i.first[0], i.first[1], pangkat(i.first[2], i.second));
          freq[{i.first[0], i.first[1], i.first[2]}] = 0;
        }
      }
      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