oj.uz

Submission #1043001

# Submission time Handle Problem Language Result Execution time Memory
1043001 2024-08-03T17:23:39 Z juicy Tourism (JOI23_tourism) C++17
0 / 100
 5000 ms 21232 KB 
#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5 + 5;

int n, m, q;
int tin[N], head[N], sz[N], s[N], c[N], res[N], pr[N];
set<array<int, 3>> st[N];
vector<int> g[N];

void upd(int i, int x) {
  for (; i <= n; i += i & -i) {
    s[i] += x;
  }
}

int qry(int i) {
  int res = 0;
  for (; i; i -= i & -i) {
    res += s[i];
  }
  return res;
}

void dfs(int u) {
  for (int &v : g[u]) {
    if (v == pr[u]) {
      swap(v, g[u].back());
      g[u].pop_back();
      break;
    }
  } 
  sz[u] = 1;
  for (int v : g[u]) {
    pr[v] = u;
    dfs(v);
    sz[u] += sz[v];
  } 
}

int order;

void hld(int u, int h) {
  tin[u] = ++order;
  head[u] = h;
  if (g[u].size()) {
    int x = *max_element(g[u].begin(), g[u].end(), [&](int i, int j) {
      return sz[i] < sz[j];
    });
    hld(x, x);
    for (int v : g[u]) {
      if (v ^ x) {
        hld(v, v);
      }
    }
  }
}

void add(int l, int r, int id, set<array<int, 3>> &st) {
  auto it = st.lower_bound(array<int, 3>{l});
  if (it != st.begin() && (*prev(it))[1] >= l) {
    --it;
  }
  for (; it != st.end() && (*it)[0] <= r; it = st.erase(it)) {
    auto [L, R, c] = *it;
    upd(c, L - R - 1);
    if (l < L) {
      upd(c, L - l);
      st.insert({l, L - 1, c});
    }
    if (R > r) {
      upd(c, R - r);
      st.insert({r + 1, R, c});
    }
  }
  upd(id, r - l + 1);
  st.insert({l, r, id});
}

void upd(int u, int v, int id) {
  for (; head[u] != head[v]; ) {
    if (sz[head[u]] > sz[head[v]]) {
      swap(u, v);
    }
    int h = head[u];
    add(tin[h], tin[u], id, st[h]);
    u = pr[h];
  }
  if (sz[u] < sz[v]) {
    swap(u, v);
  }
  if (tin[u] + 1 <= tin[v]) {
    add(tin[u] + 1, tin[v], id, st[head[u]]);
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m >> q;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1);
  hld(1, 1);
  for (int i = 1; i <= m; ++i) {
    cin >> c[i];
  }
  vector<array<int, 3>> queries;
  for (int i = 1; i <= q; ++i) {
    int l, r; cin >> l >> r;
    queries.push_back({l, r, i});
  }
  sort(queries.begin(), queries.end(), [&](auto a, auto b) {
    return a[1] < b[1];
  });
  for (int i = 1, j = 0; i <= m; ++i) {
    if (i > 1) {
      upd(c[i - 1], c[i], i);
    } 
    while (j < q && queries[j][1] == i) {
      auto [l, r, id] = queries[j++];
      res[id] = qry(r) - qry(l) + 1;
    }
  }
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Execution timed out 5055 ms 21232 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 87 ms 14228 KB Output is correct
3 Incorrect 128 ms 15452 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Incorrect 146 ms 18156 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

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