Submission #989633

#	Time	Username	Problem	Language	Result	Execution time	Memory
989633		tch1cherin	Birthday gift (IZhO18_treearray)	C++17	0 / 100	3 ms	4952 KiB

treearray

#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
• Subtask 2: 0 / 18
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44