oj.uz

Submission #989633

# Submission time Handle Problem Language Result Execution time Memory
989633 2024-05-28T12:55:19 Z tch1cherin Birthday gift (IZhO18_treearray) C++17
0 / 100
 3 ms 4952 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 200000, LG = 20;
vector<int> graph[MAX_N];
int up[MAX_N][LG];
int depth[MAX_N];

void dfs(int u, int p) {
  up[u][0] = p;
  for (int i = 1; i < LG; i++) {
    up[u][i] = up[up[u][i - 1]][i - 1];
  }
  for (int v : graph[u]) {
    if (v != p) {
      depth[v] = depth[u] + 1;
      dfs(v, u);
    }
  }
}

int lca(int u, int v) {
  if (depth[u] > depth[v]) {
    swap(u, v);
  }
  for (int i = LG - 1; i >= 0; i--) {
    if (depth[u] - (1 << i) >= depth[v]) {
      u = up[u][i];
    }
  }
  if (u == v) {
    return u;
  }
  for (int i = LG - 1; i >= 0; i--) {
    if (up[u][i] != up[v][i]) {
      u = up[u][i];
      v = up[v][i];
    }
  }
  return up[u][0];
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m, q;
  cin >> n >> m >> q;
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  vector<int> a(m);
  for (int &value : a) {
    cin >> value;
    value--;
  }
  depth[0] = 0;
  dfs(0, 0);
  vector<set<int>> S(n), Sv(n);
  for (int i = 0; i < m; i++) {
    Sv[a[i]].insert(i);
  }
  for (int i = 0; i < m - 1; i++) {
    S[lca(a[i], a[i + 1])].insert(i);
  }
  while (q--) {
    int tp;
    cin >> tp;
    if (tp == 1) {
      int pos, v;
      cin >> pos >> v;
      pos--, v--;
      Sv[a[pos]].erase(pos);
      for (int j = max(0, pos - 1); j <= pos && j < m - 1; j++) {
        S[lca(a[j], a[j + 1])].erase(j);  
      }
      a[pos] = v;
      Sv[a[pos]].insert(pos);
      for (int j = max(0, pos - 1); j <= pos && j < m - 1; j++) {
        S[lca(a[j], a[j + 1])].insert(j);
      }
    } else {
      int l, r, v;
      cin >> l >> r >> v;
      l--, v--;
      auto itv = Sv[v].lower_bound(l);
      if (itv != Sv[v].end() && *itv < r) {
        cout << *itv + 1 << " " << *itv + 1 << "\n";
      } else {
        auto it = S[v].lower_bound(l);
        if (it != S[v].end() && *it + 1 < r) {
          cout << *it + 1 << " " << *it + 2 << "\n";
        } else {
          cout << "-1 -1\n";
        }
      }
    }
  }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB n=5
2 Incorrect 3 ms 4952 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB n=5
2 Incorrect 3 ms 4952 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB n=5
2 Incorrect 3 ms 4952 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB n=5
2 Incorrect 3 ms 4952 KB Wrong range.
3 Halted 0 ms 0 KB -