oj.uz

Submission #964073

# Submission time Handle Problem Language Result Execution time Memory
964073 2024-04-16T09:32:31 Z LucaLucaM Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 105116 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <queue>
#warning That's not AS, that's my AS

typedef long long ll;

const int NMAX = 2e5;
const int DMAX = 40;

int L;

struct Node {
  int value, lazy;
};

struct segtree {
  std::vector<Node> aint;
  std::vector<int> brute;
  int n;
  segtree() {}
  segtree(int _n) {
    n = 1;
    while (n <= _n) {
      n <<= 1;
    }
    n <<= 1;
    n |= 1;
    aint.resize(n);
    for (int i = 0; i < n; i++) {
      aint[i] = {1, 1};
    }
    n = _n;
    brute.resize(n + 1, 1);
  }

  void push(int node, int tl, int tr) {
    if (aint[node].lazy != 1) {
      aint[node].value = (ll) aint[node].value * aint[node].lazy % L;
      if (tl != tr) {
        aint[2 * node].lazy = (ll) aint[node].lazy * aint[2 * node].lazy % L;
        aint[2 * node + 1].lazy = (ll) aint[node].lazy * aint[2 * node + 1].lazy % L;
      }
      aint[node].lazy = 1;
    }
  }
  void upd(int node, int tl, int tr, int l, int r, int v) {
    assert(1 <= tl && tl <= tr && tr <= n);
    push(node, tl, tr);
    if (l <= tl && tr <= r) {
      aint[node].lazy = v;
    } else {
      int mid = (tl + tr) / 2;
      if (l <= mid) {
        upd(2 * node, tl, mid, l, r, v);
      }
      if (mid < r) {
        upd(2 * node + 1, mid + 1, tr, l, r, v);
      }
      push(2 * node, tl, mid);
      push(2 * node + 1, mid + 1, tr);
      aint[node].value = (ll) aint[2 * node].value * aint[2 * node + 1].value;
    }
  }

  int qry(int node, int tl, int tr, int p) {
    push(node, tl, tr);
    if (tl == tr) {
      return aint[node].value;
    } else {
      int mid = (tl + tr) / 2;
      if (p <= mid) {
        return qry(2 * node, tl, mid, p);
      }
      return qry(2 * node + 1, mid + 1, tr, p);
    }
  }

  void bruteUpdate(int l, int r, int v) {
    for (int i = l; i <= r; i++) {
      brute[i] = (ll) brute[i] * v % L;
    }
  }
  int bruteQuery(int p) {
    return brute[p];
  }

  void update(int l, int r, int v) {
    if (l > r) {
      return;
    }
    if (r - l <= 15) {
      bruteUpdate(l, r, v);
    } else {
      upd(1, 1, n, l, r, v);
    }
  }
  int query(int p) {
    return (ll) bruteQuery(p) * qry(1, 1, n, p);
  }
};

std::vector<int> g[NMAX + 1];
int parent[NMAX + 1];
int Time[NMAX + 1];
int timer;
int lt[NMAX + 1][DMAX + 1];
int rt[NMAX + 1][DMAX + 1];

void bfs() {
  std::queue<int> q;
  q.push(1);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    Time[u] = ++timer;
    std::vector<int> newG;
    for (const auto &v : g[u]) {
      if (!Time[v]) {
        parent[v] = u;
        newG.push_back(v);
        q.push(v);
      }
    }
    g[u] = newG;
  }
}

void dfs(int u) {
  lt[u][0] = rt[u][0] = Time[u];
  for (int d = 1; d <= DMAX; d++) {
    lt[u][d] = NMAX + 1;
    rt[u][d] = 0;
  }
  for (const auto &v : g[u]) {
    assert(v != parent[u]);
    dfs(v);
    for (int d = 0; d < DMAX; d++) {
      lt[u][d + 1] = std::min(lt[u][d + 1], lt[v][d]);
      rt[u][d + 1] = std::max(rt[u][d + 1], rt[v][d]);
    }
  }
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);

  int n;
  std::cin >> n >> L;

  for (int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  bfs();
  dfs(1);

  segtree aint(n);

  for (int i = 1; i <= n; i++) {
    int h;
    std::cin >> h;
    aint.update(Time[i], Time[i], h);
  }

  int q;
  std::cin >> q;

  while (q--) {
    int type;
    std::cin >> type;
    if (type == 1) {
      int u, d, h;
      std::cin >> u >> d >> h;
      std::vector<std::pair<int, int>> ancestors;
      int v = u;
      for (int i = 0; i <= d && v != 0; i++) {
        ancestors.push_back({v, d - i});
        v = parent[v];
      }
      std::reverse(ancestors.begin(), ancestors.end());
      int maxDepth = -1;
      for (const auto &[v, depth] : ancestors) {
        /// i + depth > maxDepth => i > maxDepth - depth
        /// i + d - depth <= d <=> i <= depth
        for (int i = std::max(0, maxDepth - depth + 1); i <= depth; i++) {
          aint.update(lt[v][i], rt[v][i], h);
          maxDepth = i + depth;
        }
      }
    } else {
      int u;
      std::cin >> u;
      std::cout << aint.query(Time[u]) << '\n';
    }
  }

  return 0;
}

Compilation message

sprinkler.cpp:7:2: warning: #warning That's not AS, that's my AS [-Wcpp]
    7 | #warning That's not AS, that's my AS
      |  ^~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 3 ms 9048 KB Output is correct
4 Correct 4 ms 9280 KB Output is correct
5 Incorrect 3 ms 9180 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 392 ms 90332 KB Output is correct
3 Correct 406 ms 88932 KB Output is correct
4 Correct 428 ms 99256 KB Output is correct
5 Correct 375 ms 89440 KB Output is correct
6 Correct 391 ms 89476 KB Output is correct
7 Incorrect 381 ms 89756 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 392 ms 90332 KB Output is correct
3 Correct 406 ms 88932 KB Output is correct
4 Correct 428 ms 99256 KB Output is correct
5 Correct 375 ms 89440 KB Output is correct
6 Correct 391 ms 89476 KB Output is correct
7 Incorrect 381 ms 89756 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 532 ms 97816 KB Output is correct
3 Correct 1745 ms 95592 KB Output is correct
4 Correct 758 ms 103056 KB Output is correct
5 Correct 1237 ms 91204 KB Output is correct
6 Correct 2238 ms 91332 KB Output is correct
7 Correct 1455 ms 91876 KB Output is correct
8 Correct 374 ms 92288 KB Output is correct
9 Correct 570 ms 101524 KB Output is correct
10 Correct 1601 ms 105116 KB Output is correct
11 Correct 780 ms 90884 KB Output is correct
12 Correct 3753 ms 92008 KB Output is correct
13 Execution timed out 4091 ms 89752 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 561 ms 95552 KB Output is correct
3 Correct 1657 ms 92384 KB Output is correct
4 Correct 807 ms 101824 KB Output is correct
5 Incorrect 1169 ms 93036 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 3 ms 9048 KB Output is correct
4 Correct 4 ms 9280 KB Output is correct
5 Incorrect 3 ms 9180 KB Output isn't correct
6 Halted 0 ms 0 KB -