oj.uz

Submission #637995

# Submission time Handle Problem Language Result Execution time Memory
637995 2022-09-04T06:42:35 Z tvladm2009 Birthday gift (IZhO18_treearray) C++14
0 / 100
 11 ms 23808 KB 
#include <bits/stdc++.h>

const int MAX_N = 2 * 1e5;
const int MAX_L = 19;

std::vector<int> g[MAX_N + 1];
int a[MAX_N + 1], up[MAX_N + 1][MAX_L + 1], l[MAX_N + 1], r[MAX_N + 1];
std::set<int> one[MAX_N + 1], two[MAX_N + 1];
int t = 0;

void dfs(int u, int p) {
  up[u][0] = p;
  for (int i = 1; i <= MAX_L; i++) {
    up[u][i] = up[up[u][i - 1]][i - 1];
  }
  l[u] = ++t;
  for (int v : g[u]) {
    if (v != p) {
      dfs(v, u);
    }
  }
  r[u] = ++t;
}

bool is_ancestor(int u, int v) {
  return l[u] <= l[v] && r[v] <= r[u];
}

int lca(int u, int v) {
  if (is_ancestor(u, v)) {
    return v;
  } else if (is_ancestor(v, u)) {
    return u;
  }
  for (int i = MAX_L; i >= 0; i--) {
    if (!is_ancestor(up[u][i], v)) {
      u = up[u][i];
    }
  }
  return up[u][0];
}

int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);
  int n, m, q;
  std::cin >> n >> m >> q;
  for (int i = 1; i <= n - 1; i++) {
    int x, y;
    std::cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1, 1);
  for (int i = 1; i <= m; i++) {
    std::cin >> a[i];
    one[a[i]].insert(i);
    if (i > 1) {
      std::cout << a[i - 1] << " " << a[i] << " " << lca(a[i - 1], a[i]) << "\n";
      two[lca(a[i - 1], a[i])].insert(i - 1);
    }
  }
  for (int i = 1; i <= q; i++) {
    int type = 0;
    std::cin >> type;
    if (type == 1) {
      int pos, v;
      std::cin >> pos >> v;
      one[a[pos]].erase(pos);
      if (pos > 1) {
        two[lca(a[pos - 1], a[pos])].erase(pos - 1);
      }
      if (pos < m) {
        two[lca(a[pos], a[pos + 1])].erase(pos);
      }
      a[pos] = v;
      one[a[pos]].insert(pos);
      if (pos > 1) {
        two[lca(a[pos - 1], a[pos])].insert(pos - 1);
      }
      if (pos < m) {
        two[lca(a[pos], a[pos + 1])].insert(pos);
      }
    } else {
      int l, r, v;
      std::cin >> l >> r >> v;
      auto it = one[v].lower_bound(l);
      if (it != one[v].end() && (*it) <= r) {
        std::cout << (*it) << " " << (*it) << "\n";
        continue;
      }
      it = two[v].lower_bound(l);
      if (it != two[v].end() && (*it) + 1 <= r) {
        std::cout << (*it) << " " << (*it) + 1 << "\n";
        continue;
      }
      std::cout << "-1 -1\n";
    }
  }
  return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23808 KB Wrong output format.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23808 KB Wrong output format.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23808 KB Wrong output format.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 23808 KB Wrong output format.
2 Halted 0 ms 0 KB -