oj.uz

Submission #988663

# Submission time Handle Problem Language Result Execution time Memory
988663 2024-05-25T12:15:37 Z mannshah1211 Birthday gift (IZhO18_treearray) C++17
100 / 100
 1200 ms 91740 KB 
/**
 *    author: tourist
 *    created:
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template <typename T>
class graph {
 public:
  struct edge {
    int from;
    int to;
    T cost;
  };

  vector<edge> edges;
  vector<vector<int>> g;
  int n;

  graph(int _n) : n(_n) {
    g.resize(n);
  }

  virtual int add(int from, int to, T cost) = 0;
};

template <typename T>
class forest : public graph<T> {
 public:
  using graph<T>::edges;
  using graph<T>::g;
  using graph<T>::n;

  forest(int _n) : graph<T>(_n) {
  }

  int add(int from, int to, T cost = 1) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int) edges.size();
    assert(id < n - 1);
    g[from].push_back(id);
    g[to].push_back(id);
    edges.push_back({from, to, cost});
    return id;
  }
};

template <typename T>
class dfs_forest : public forest<T> {
 public:
  using forest<T>::edges;
  using forest<T>::g;
  using forest<T>::n;

  vector<int> pv;
  vector<int> pe;
  vector<int> order;
  vector<int> pos;
  vector<int> end;
  vector<int> sz;
  vector<int> root;
  vector<int> depth;
  vector<T> dist;

  dfs_forest(int _n) : forest<T>(_n) {
  }

  void init() {
    pv = vector<int>(n, -1);
    pe = vector<int>(n, -1);
    order.clear();
    pos = vector<int>(n, -1);
    end = vector<int>(n, -1);
    sz = vector<int>(n, 0);
    root = vector<int>(n, -1);
    depth = vector<int>(n, -1);
    dist = vector<T>(n);
  }

  void clear() {
    pv.clear();
    pe.clear();
    order.clear();
    pos.clear();
    end.clear();
    sz.clear();
    root.clear();
    depth.clear();
    dist.clear();
  }

 private:
  void do_dfs(int v) {
    pos[v] = (int) order.size();
    order.push_back(v);
    sz[v] = 1;
    for (int id : g[v]) {
      if (id == pe[v]) {
        continue;
      }
      auto &e = edges[id];
      int to = e.from ^ e.to ^ v;
      depth[to] = depth[v] + 1;
      dist[to] = dist[v] + e.cost;
      pv[to] = v;
      pe[to] = id;
      root[to] = (root[v] != -1 ? root[v] : to);
      do_dfs(to);
      sz[v] += sz[to];
    }
    end[v] = (int) order.size() - 1;
  }

  void do_dfs_from(int v) {
    depth[v] = 0;
    dist[v] = T{};
    root[v] = v;
    pv[v] = pe[v] = -1;
    do_dfs(v);
  }

 public:
  void dfs(int v, bool clear_order = true) {
    if (pv.empty()) {
      init();
    } else {
      if (clear_order) {
        order.clear();
      }
    }
    do_dfs_from(v);
  }

  void dfs_all() {
    init();
    for (int v = 0; v < n; v++) {
      if (depth[v] == -1) {
        do_dfs_from(v);
      }
    }
    assert((int) order.size() == n);
  }
};

template <typename T>
class lca_forest : public dfs_forest<T> {
 public:
  using dfs_forest<T>::edges;
  using dfs_forest<T>::g;
  using dfs_forest<T>::n;
  using dfs_forest<T>::pv;
  using dfs_forest<T>::pos;
  using dfs_forest<T>::end;
  using dfs_forest<T>::depth;

  int h;
  vector<vector<int>> pr;

  lca_forest(int _n) : dfs_forest<T>(_n) {
  }

  inline void build_lca() {
    assert(!pv.empty());
    int max_depth = 0;
    for (int i = 0; i < n; i++) {
      max_depth = max(max_depth, depth[i]);
    }
    h = 1;
    while ((1 << h) <= max_depth) {
      h++;
    }
    pr.resize(n);
    for (int i = 0; i < n; i++) {
      pr[i].resize(h);
      pr[i][0] = pv[i];
    }
    for (int j = 1; j < h; j++) {
      for (int i = 0; i < n; i++) {
        pr[i][j] = (pr[i][j - 1] == -1 ? -1 : pr[pr[i][j - 1]][j - 1]);
      }
    }
  }

  inline bool anc(int x, int y) {
    return (pos[x] <= pos[y] && end[y] <= end[x]);
  }

  inline int go_up(int x, int up) {
    assert(!pr.empty());
    up = min(up, (1 << h) - 1);
    for (int j = h - 1; j >= 0; j--) {
      if (up & (1 << j)) {
        x = pr[x][j];
        if (x == -1) {
          break;
        }
      }
    }
    return x;
  }

  inline int lca(int x, int y) {
    assert(!pr.empty());
    if (anc(x, y)) {
      return x;
    }
    if (anc(y, x)) {
      return y;
    }
    for (int j = h - 1; j >= 0; j--) {
      if (pr[x][j] != -1 && !anc(pr[x][j], y)) {
        x = pr[x][j];
      }
    }
    return pr[x][0];
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, q;
  cin >> n >> m >> q;
  lca_forest<int> g(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    g.add(u, v);
  }
  g.dfs_all();
  g.build_lca();
  vector<int> a(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i];
    --a[i];
  }
  vector<set<pair<int, int>>> at(n);
  for (int i = 0; i < m - 1; i++) {
    at[g.lca(a[i], a[i + 1])].insert(make_pair(i, i + 1));
  }
  for (int i = 0; i < m; i++) {
    at[a[i]].insert(make_pair(i, i));
  }
  auto Add = [&](int p) -> void {
    at[a[p]].insert(make_pair(p, p));
    if (p > 0) {
      at[g.lca(a[p - 1], a[p])].insert(make_pair(p - 1, p));
    }
    if (p < m - 1) {
      at[g.lca(a[p], a[p + 1])].insert(make_pair(p, p + 1));
    }
  };
  auto Remove = [&](int p) -> void {
    at[a[p]].erase(make_pair(p, p));
    if (p > 0) {
      at[g.lca(a[p - 1], a[p])].erase(make_pair(p - 1, p));
    }
    if (p < m - 1) {
      at[g.lca(a[p], a[p + 1])].erase(make_pair(p, p + 1));
    }
  };
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int p, v;
      cin >> p >> v;
      --p; --v;
      Remove(p);
      a[p] = v;
      Add(p);
    } else {
      int l, r, v;
      cin >> l >> r >> v;
      --l; --r; --v;
      auto it = at[v].lower_bound(make_pair(l, l));
      if (it == at[v].end() || it->second > r) {
        cout << -1 << " " << -1 << '\n';
      } else {
        cout << it->first + 1 << " " << it->second + 1 << '\n';
      }
    }
  }
  return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n=5
2 Correct 1 ms 344 KB n=100
3 Correct 1 ms 348 KB n=100
4 Correct 1 ms 348 KB n=100
5 Correct 1 ms 348 KB n=100
6 Correct 1 ms 344 KB n=100
7 Correct 1 ms 348 KB n=100
8 Correct 1 ms 348 KB n=100
9 Correct 1 ms 348 KB n=100
10 Correct 1 ms 348 KB n=100
11 Correct 1 ms 348 KB n=100
12 Correct 1 ms 348 KB n=100
13 Correct 1 ms 348 KB n=100
14 Correct 1 ms 600 KB n=100
15 Correct 1 ms 500 KB n=100
16 Correct 1 ms 348 KB n=100
17 Correct 1 ms 348 KB n=100
18 Correct 1 ms 344 KB n=100
19 Correct 1 ms 348 KB n=100
20 Correct 1 ms 348 KB n=100
21 Correct 1 ms 548 KB n=100
22 Correct 1 ms 600 KB n=100
23 Correct 1 ms 348 KB n=100
24 Correct 1 ms 344 KB n=100
25 Correct 1 ms 620 KB n=100
26 Correct 1 ms 348 KB n=12
27 Correct 1 ms 348 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n=5
2 Correct 1 ms 344 KB n=100
3 Correct 1 ms 348 KB n=100
4 Correct 1 ms 348 KB n=100
5 Correct 1 ms 348 KB n=100
6 Correct 1 ms 344 KB n=100
7 Correct 1 ms 348 KB n=100
8 Correct 1 ms 348 KB n=100
9 Correct 1 ms 348 KB n=100
10 Correct 1 ms 348 KB n=100
11 Correct 1 ms 348 KB n=100
12 Correct 1 ms 348 KB n=100
13 Correct 1 ms 348 KB n=100
14 Correct 1 ms 600 KB n=100
15 Correct 1 ms 500 KB n=100
16 Correct 1 ms 348 KB n=100
17 Correct 1 ms 348 KB n=100
18 Correct 1 ms 344 KB n=100
19 Correct 1 ms 348 KB n=100
20 Correct 1 ms 348 KB n=100
21 Correct 1 ms 548 KB n=100
22 Correct 1 ms 600 KB n=100
23 Correct 1 ms 348 KB n=100
24 Correct 1 ms 344 KB n=100
25 Correct 1 ms 620 KB n=100
26 Correct 1 ms 348 KB n=12
27 Correct 1 ms 348 KB n=100
28 Correct 1 ms 604 KB n=500
29 Correct 1 ms 856 KB n=500
30 Correct 1 ms 604 KB n=500
31 Correct 1 ms 604 KB n=500
32 Correct 1 ms 604 KB n=500
33 Correct 1 ms 600 KB n=500
34 Correct 1 ms 604 KB n=500
35 Correct 1 ms 604 KB n=500
36 Correct 1 ms 604 KB n=500
37 Correct 2 ms 604 KB n=500
38 Correct 1 ms 464 KB n=500
39 Correct 1 ms 600 KB n=500
40 Correct 1 ms 600 KB n=500
41 Correct 1 ms 600 KB n=500
42 Correct 1 ms 600 KB n=500
43 Correct 2 ms 604 KB n=500
44 Correct 1 ms 604 KB n=500
45 Correct 1 ms 604 KB n=500
46 Correct 1 ms 604 KB n=500
47 Correct 1 ms 856 KB n=500
48 Correct 2 ms 604 KB n=500
49 Correct 1 ms 604 KB n=500
50 Correct 1 ms 604 KB n=500
51 Correct 2 ms 748 KB n=500
52 Correct 1 ms 604 KB n=500
53 Correct 1 ms 604 KB n=500
54 Correct 1 ms 600 KB n=500
55 Correct 1 ms 348 KB n=278
56 Correct 1 ms 604 KB n=500
57 Correct 1 ms 604 KB n=500
58 Correct 1 ms 604 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n=5
2 Correct 1 ms 344 KB n=100
3 Correct 1 ms 348 KB n=100
4 Correct 1 ms 348 KB n=100
5 Correct 1 ms 348 KB n=100
6 Correct 1 ms 344 KB n=100
7 Correct 1 ms 348 KB n=100
8 Correct 1 ms 348 KB n=100
9 Correct 1 ms 348 KB n=100
10 Correct 1 ms 348 KB n=100
11 Correct 1 ms 348 KB n=100
12 Correct 1 ms 348 KB n=100
13 Correct 1 ms 348 KB n=100
14 Correct 1 ms 600 KB n=100
15 Correct 1 ms 500 KB n=100
16 Correct 1 ms 348 KB n=100
17 Correct 1 ms 348 KB n=100
18 Correct 1 ms 344 KB n=100
19 Correct 1 ms 348 KB n=100
20 Correct 1 ms 348 KB n=100
21 Correct 1 ms 548 KB n=100
22 Correct 1 ms 600 KB n=100
23 Correct 1 ms 348 KB n=100
24 Correct 1 ms 344 KB n=100
25 Correct 1 ms 620 KB n=100
26 Correct 1 ms 348 KB n=12
27 Correct 1 ms 348 KB n=100
28 Correct 1 ms 604 KB n=500
29 Correct 1 ms 856 KB n=500
30 Correct 1 ms 604 KB n=500
31 Correct 1 ms 604 KB n=500
32 Correct 1 ms 604 KB n=500
33 Correct 1 ms 600 KB n=500
34 Correct 1 ms 604 KB n=500
35 Correct 1 ms 604 KB n=500
36 Correct 1 ms 604 KB n=500
37 Correct 2 ms 604 KB n=500
38 Correct 1 ms 464 KB n=500
39 Correct 1 ms 600 KB n=500
40 Correct 1 ms 600 KB n=500
41 Correct 1 ms 600 KB n=500
42 Correct 1 ms 600 KB n=500
43 Correct 2 ms 604 KB n=500
44 Correct 1 ms 604 KB n=500
45 Correct 1 ms 604 KB n=500
46 Correct 1 ms 604 KB n=500
47 Correct 1 ms 856 KB n=500
48 Correct 2 ms 604 KB n=500
49 Correct 1 ms 604 KB n=500
50 Correct 1 ms 604 KB n=500
51 Correct 2 ms 748 KB n=500
52 Correct 1 ms 604 KB n=500
53 Correct 1 ms 604 KB n=500
54 Correct 1 ms 600 KB n=500
55 Correct 1 ms 348 KB n=278
56 Correct 1 ms 604 KB n=500
57 Correct 1 ms 604 KB n=500
58 Correct 1 ms 604 KB n=500
59 Correct 3 ms 1112 KB n=2000
60 Correct 3 ms 1116 KB n=2000
61 Correct 3 ms 1112 KB n=2000
62 Correct 3 ms 1116 KB n=2000
63 Correct 3 ms 1116 KB n=2000
64 Correct 3 ms 1116 KB n=2000
65 Correct 3 ms 1116 KB n=2000
66 Correct 3 ms 1116 KB n=2000
67 Correct 3 ms 1116 KB n=2000
68 Correct 3 ms 1116 KB n=2000
69 Correct 3 ms 1116 KB n=2000
70 Correct 3 ms 1116 KB n=2000
71 Correct 3 ms 1116 KB n=2000
72 Correct 3 ms 1116 KB n=2000
73 Correct 4 ms 1368 KB n=2000
74 Correct 3 ms 860 KB n=1844
75 Correct 3 ms 1116 KB n=2000
76 Correct 3 ms 1112 KB n=2000
77 Correct 3 ms 1116 KB n=2000
78 Correct 3 ms 1112 KB n=2000
79 Correct 3 ms 1116 KB n=2000
80 Correct 3 ms 1624 KB n=2000
81 Correct 4 ms 980 KB n=2000
82 Correct 3 ms 1112 KB n=2000
83 Correct 3 ms 1116 KB n=2000
84 Correct 3 ms 1116 KB n=2000
85 Correct 3 ms 1156 KB n=2000
86 Correct 3 ms 1112 KB n=2000
87 Correct 3 ms 1116 KB n=2000
88 Correct 3 ms 1116 KB n=2000
89 Correct 3 ms 1112 KB n=2000
90 Correct 3 ms 1116 KB n=2000
91 Correct 3 ms 1116 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n=5
2 Correct 1 ms 344 KB n=100
3 Correct 1 ms 348 KB n=100
4 Correct 1 ms 348 KB n=100
5 Correct 1 ms 348 KB n=100
6 Correct 1 ms 344 KB n=100
7 Correct 1 ms 348 KB n=100
8 Correct 1 ms 348 KB n=100
9 Correct 1 ms 348 KB n=100
10 Correct 1 ms 348 KB n=100
11 Correct 1 ms 348 KB n=100
12 Correct 1 ms 348 KB n=100
13 Correct 1 ms 348 KB n=100
14 Correct 1 ms 600 KB n=100
15 Correct 1 ms 500 KB n=100
16 Correct 1 ms 348 KB n=100
17 Correct 1 ms 348 KB n=100
18 Correct 1 ms 344 KB n=100
19 Correct 1 ms 348 KB n=100
20 Correct 1 ms 348 KB n=100
21 Correct 1 ms 548 KB n=100
22 Correct 1 ms 600 KB n=100
23 Correct 1 ms 348 KB n=100
24 Correct 1 ms 344 KB n=100
25 Correct 1 ms 620 KB n=100
26 Correct 1 ms 348 KB n=12
27 Correct 1 ms 348 KB n=100
28 Correct 1 ms 604 KB n=500
29 Correct 1 ms 856 KB n=500
30 Correct 1 ms 604 KB n=500
31 Correct 1 ms 604 KB n=500
32 Correct 1 ms 604 KB n=500
33 Correct 1 ms 600 KB n=500
34 Correct 1 ms 604 KB n=500
35 Correct 1 ms 604 KB n=500
36 Correct 1 ms 604 KB n=500
37 Correct 2 ms 604 KB n=500
38 Correct 1 ms 464 KB n=500
39 Correct 1 ms 600 KB n=500
40 Correct 1 ms 600 KB n=500
41 Correct 1 ms 600 KB n=500
42 Correct 1 ms 600 KB n=500
43 Correct 2 ms 604 KB n=500
44 Correct 1 ms 604 KB n=500
45 Correct 1 ms 604 KB n=500
46 Correct 1 ms 604 KB n=500
47 Correct 1 ms 856 KB n=500
48 Correct 2 ms 604 KB n=500
49 Correct 1 ms 604 KB n=500
50 Correct 1 ms 604 KB n=500
51 Correct 2 ms 748 KB n=500
52 Correct 1 ms 604 KB n=500
53 Correct 1 ms 604 KB n=500
54 Correct 1 ms 600 KB n=500
55 Correct 1 ms 348 KB n=278
56 Correct 1 ms 604 KB n=500
57 Correct 1 ms 604 KB n=500
58 Correct 1 ms 604 KB n=500
59 Correct 3 ms 1112 KB n=2000
60 Correct 3 ms 1116 KB n=2000
61 Correct 3 ms 1112 KB n=2000
62 Correct 3 ms 1116 KB n=2000
63 Correct 3 ms 1116 KB n=2000
64 Correct 3 ms 1116 KB n=2000
65 Correct 3 ms 1116 KB n=2000
66 Correct 3 ms 1116 KB n=2000
67 Correct 3 ms 1116 KB n=2000
68 Correct 3 ms 1116 KB n=2000
69 Correct 3 ms 1116 KB n=2000
70 Correct 3 ms 1116 KB n=2000
71 Correct 3 ms 1116 KB n=2000
72 Correct 3 ms 1116 KB n=2000
73 Correct 4 ms 1368 KB n=2000
74 Correct 3 ms 860 KB n=1844
75 Correct 3 ms 1116 KB n=2000
76 Correct 3 ms 1112 KB n=2000
77 Correct 3 ms 1116 KB n=2000
78 Correct 3 ms 1112 KB n=2000
79 Correct 3 ms 1116 KB n=2000
80 Correct 3 ms 1624 KB n=2000
81 Correct 4 ms 980 KB n=2000
82 Correct 3 ms 1112 KB n=2000
83 Correct 3 ms 1116 KB n=2000
84 Correct 3 ms 1116 KB n=2000
85 Correct 3 ms 1156 KB n=2000
86 Correct 3 ms 1112 KB n=2000
87 Correct 3 ms 1116 KB n=2000
88 Correct 3 ms 1116 KB n=2000
89 Correct 3 ms 1112 KB n=2000
90 Correct 3 ms 1116 KB n=2000
91 Correct 3 ms 1116 KB n=2000
92 Correct 723 ms 68952 KB n=200000
93 Correct 1136 ms 85008 KB n=200000
94 Correct 693 ms 89340 KB n=200000
95 Correct 660 ms 68904 KB n=200000
96 Correct 575 ms 69276 KB n=200000
97 Correct 1093 ms 84232 KB n=200000
98 Correct 560 ms 68780 KB n=200000
99 Correct 836 ms 69200 KB n=200000
100 Correct 766 ms 68864 KB n=200000
101 Correct 621 ms 91740 KB n=200000
102 Correct 399 ms 70132 KB n=200000
103 Correct 388 ms 70148 KB n=200000
104 Correct 391 ms 70168 KB n=200000
105 Correct 364 ms 70576 KB n=200000
106 Correct 339 ms 70632 KB n=200000
107 Correct 346 ms 70848 KB n=200000
108 Correct 812 ms 69228 KB n=200000
109 Correct 661 ms 69008 KB n=200000
110 Correct 923 ms 69496 KB n=200000
111 Correct 738 ms 68280 KB n=200000
112 Correct 754 ms 89864 KB n=200000
113 Correct 1087 ms 84384 KB n=200000
114 Correct 758 ms 68608 KB n=200000
115 Correct 1200 ms 81384 KB n=200000
116 Correct 690 ms 69068 KB n=200000
117 Correct 738 ms 90444 KB n=200000
118 Correct 1178 ms 82208 KB n=200000
119 Correct 653 ms 69116 KB n=200000
120 Correct 568 ms 90004 KB n=200000
121 Correct 602 ms 90876 KB n=200000
122 Correct 582 ms 90296 KB n=200000
123 Correct 390 ms 70876 KB n=200000
124 Correct 104 ms 19088 KB n=25264