oj.uz

Submission #848030

# Submission time Handle Problem Language Result Execution time Memory
848030 2023-09-11T05:49:27 Z NeroZein Sprinkler (JOI22_sprinkler) C++17
0 / 100
 546 ms 57256 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int D = 41;
const int N = 2e5 + 5;

int dp[N][D]; 
int parent[N]; 
vector<int> g[N]; 

void dfs(int v, int p) {
  parent[v] = p;
  for (int u : g[v]) if (u != p) dfs(u, v);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, l;
  cin >> n >> l;
  for(int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 0);
  for (int i = 0; i < D; ++i) {
    fill(dp[i], dp[i] + D, 1); 
  }
  for (int i = 1; i <= n; ++i) {
    cin >> dp[i][0];
  }
  auto mul = [&](int x, int y) {
    return (int) ((long long) x * y % l); 
  };
  int q;
  cin >> q;
  while (q--) {
    int t, v;
    cin >> t >> v;
    if (t == 1) {
      int d, w;
      cin >> d >> w;
      while (d > 0 && v != 1) {
        dp[v][d] = mul(dp[v][d], w);//if the distance is d - 1, to parent will be d + 1 
        dp[v][d - 1] = mul(dp[v][d - 1], w);
        d--;
        v = parent[v];
      }
      for (int i = 0; i <= d; ++i) {
        dp[v][i] = mul(dp[v][i], w); 
      }
    } else {
      int ans = 1;
      for (int i = 0; i < D && v; ++i, v = parent[v]) {
        ans = mul(ans, dp[v][i]);
      }
      cout << ans << '\n'; 
    }
  }
  return 0;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Incorrect 325 ms 53112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Incorrect 325 ms 53112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6804 KB Output is correct
2 Incorrect 546 ms 57256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6800 KB Output is correct
2 Incorrect 488 ms 55732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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