oj.uz

Submission #1000516

# Submission time Handle Problem Language Result Execution time Memory
1000516 2024-06-17T16:21:01 Z LucaLucaM Tourism (JOI23_tourism) C++17
0 / 100
 5000 ms 16952 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#warning That's the baby, that's not my baby

typedef long long ll;

const int NMAX = 100'000;
const int LGMAX = 18;

std::vector<int> g[NMAX + 1];
int parent[NMAX + 1];
int tin[NMAX + 1], tout[NMAX + 1], timer;

int jump[LGMAX + 1][NMAX + 1];

void dfs(int u) {
  tin[u] = ++timer;
  for (const auto &v : g[u]) {
    if (v != parent[u]) {
      parent[v] = u;
      dfs(v);
    }
  }
  tout[u] = ++timer;
}

bool ancestor(int u, int v) {
  return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
  if (ancestor(u, v)) {
    return u;
  }
  for (int k = LGMAX; k >= 0; k--) {
    if (jump[k][u] != 0 && !ancestor(jump[k][u], v)) {
      u = jump[k][u];
    }
  }
  return jump[0][u];
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n, m, q;
  std::cin >> n >> m >> q;

  for (int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  dfs(1);

  for (int i = 1; i <= n; i++) {
    jump[0][i] = parent[i];
  }
  for (int j = 1; j <= LGMAX; j++) {
    for (int i = 1; i <= n; i++) {
      jump[j][i] = jump[j - 1][jump[j - 1][i]];
    }
  }

  std::vector<int> a(m);
  for (auto &x : a) {
    std::cin >> x;
  }
  a.insert(a.begin(), 0);

  while (q--) {
    int l, r;
    std::cin >> l >> r;
    std::vector<bool> vis(n + 1, false);
    std::vector<int> nodes;
    for (int i = l; i <= r; i++) {
      nodes.push_back(a[i]);
    }
    std::sort(nodes.begin(), nodes.end(), [&](int x, int y) {
       return tin[x] < tin[y];
    });
    int w = -1;
    for (const auto &node : nodes) {
      if (w == -1) {
        w = node;
      } else {
        w = lca(w, node);
      }
      int u = node;
      while (u != w) {
        vis[u] = true;
        u = parent[u];
      }
      assert(u == w);
      vis[u] = true;
    }
    std::cout << std::count(vis.begin(), vis.end(), true) << '\n';
  }

  return 0;
}

Compilation message

tourism.cpp:6:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    6 | #warning That's the baby, that's not my baby
      |  ^~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9180 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Incorrect 1 ms 9052 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9180 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Incorrect 1 ms 9052 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9180 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 15 ms 9268 KB Output is correct
4 Execution timed out 5072 ms 16952 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9052 KB Output is correct
2 Incorrect 100 ms 13660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 2 ms 9184 KB Output is correct
3 Correct 15 ms 9048 KB Output is correct
4 Execution timed out 5098 ms 14912 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9180 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Incorrect 1 ms 9052 KB Output isn't correct
4 Halted 0 ms 0 KB -