oj.uz

Submission #964046

# Submission time Handle Problem Language Result Execution time Memory
964046 2024-04-16T08:54:49 Z LucaLucaM Sprinkler (JOI22_sprinkler) C++17
9 / 100
 639 ms 36604 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;

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) {
//    bruteUpdate(l, r, v);
    upd(1, 1, n, l, r, v);
  }
  int query(int p) {
//    return bruteQuery(p);
    return qry(1, 1, n, p);
  }
};

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

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

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.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();

//  std::cout << " > ";
//  for (int i = 1; i <= n; i++) {
//    std::cout << Time[i] << ' ';
//  }
//  std::cout << '\n';

  segtree aint(2 * n + 1);

  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;
      assert(d <= 1);
      aint.update(Time[u], Time[u], h);
      if (d == 1) {
        if (!g[u].empty()) {
          int l = Time[g[u][0]];
          int r = Time[g[u].back()];
          aint.update(l, r, h);
        }
        if (u != 1) {
          int v = parent[u];
          aint.update(Time[v], Time[v], h);
        }
      }
    } 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 Runtime error 6 ms 12892 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 283 ms 34604 KB Output is correct
3 Correct 588 ms 35152 KB Output is correct
4 Correct 406 ms 34668 KB Output is correct
5 Correct 333 ms 35096 KB Output is correct
6 Correct 347 ms 34368 KB Output is correct
7 Correct 367 ms 35228 KB Output is correct
8 Correct 301 ms 36604 KB Output is correct
9 Correct 329 ms 34108 KB Output is correct
10 Correct 562 ms 34780 KB Output is correct
11 Correct 284 ms 34580 KB Output is correct
12 Correct 555 ms 35044 KB Output is correct
13 Correct 548 ms 36392 KB Output is correct
14 Correct 639 ms 36000 KB Output is correct
15 Correct 613 ms 35548 KB Output is correct
16 Correct 525 ms 36008 KB Output is correct
17 Correct 625 ms 36444 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 2 ms 6552 KB Output is correct
20 Correct 2 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 2 ms 6492 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 283 ms 34604 KB Output is correct
3 Correct 588 ms 35152 KB Output is correct
4 Correct 406 ms 34668 KB Output is correct
5 Correct 333 ms 35096 KB Output is correct
6 Correct 347 ms 34368 KB Output is correct
7 Correct 367 ms 35228 KB Output is correct
8 Correct 301 ms 36604 KB Output is correct
9 Correct 329 ms 34108 KB Output is correct
10 Correct 562 ms 34780 KB Output is correct
11 Correct 284 ms 34580 KB Output is correct
12 Correct 555 ms 35044 KB Output is correct
13 Correct 548 ms 36392 KB Output is correct
14 Correct 639 ms 36000 KB Output is correct
15 Correct 613 ms 35548 KB Output is correct
16 Correct 525 ms 36008 KB Output is correct
17 Correct 625 ms 36444 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 2 ms 6552 KB Output is correct
20 Correct 2 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 2 ms 6492 KB Output is correct
23 Runtime error 7 ms 12892 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 12892 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 12892 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 12892 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -