oj.uz

Submission #1030763

# Submission time Handle Problem Language Result Execution time Memory
1030763 2024-07-22T09:38:41 Z NeroZein Tourism (JOI23_tourism) C++17
0 / 100
 488 ms 15188 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 1e5 + 5; 

int c[N]; 
int bit[N];
int ans[N];
vector<int> g[N];
set<array<int, 3>> se; 
int idd, id[N], top[N];
int sz[N], pr[N], dep[N];
vector<pair<int, int>> qs[N];

void dfs(int v, int p) {
  sz[v] = 1; 
  for (int u : g[v]) {
    if (u == p) {
      continue; 
    }
    pr[u] = v;
    dep[u] = dep[v] + 1; 
    dfs(u, v);
    sz[v] += sz[u]; 
  }
}

void dfs_hld(int v, int p, int tp) {
  top[v] = tp;
  id[v] = ++idd; 
  int heavy = 0;
  for (int u : g[v]) {
    if (u != p && sz[u] > sz[heavy]) {
      heavy = u;
    }
  }
  if (heavy) {
    dfs_hld(heavy, v, tp);
  }
  for (int u : g[v]) {
    if (u != p && u != heavy) {
      dfs_hld(u, v, u); 
    }
  }
}

void upd(int i, int v) {
  while (i < N) {
    bit[i] += v;
    i += i & -i;
  }
}

int qry(int i) {
  int ret = 0;
  while (i) {
    ret += bit[i];
    i -= i & -i;
  }
  return ret;
}

int qry(int l, int r) {
  return qry(r) - qry(l - 1); 
}

void ins(int l, int r, int val) {
  vector<array<int, 3>> pp, psh;
  psh.push_back({l, r, val});
  auto itr = prev(se.upper_bound({l, INT_MAX, INT_MAX}));
  if ((*itr) [1] >= l) {
    pp.push_back(*itr);
    if ((*itr)[0] < l) {
      psh.push_back({(*itr)[0], l - 1, (*itr)[2]});
    }
  }
  itr++;
  while (itr != se.end() && (*itr)[0] <= r) {
    //debug((*itr)[0]);
    pp.push_back(*itr);
    if ((*itr)[1] > r) {
      psh.push_back({r + 1, (*itr)[1], (*itr)[2]});
    }
    itr++;
  }
  //debug(l, r, val);
  for (auto [xl, xr, xv] : pp) {
    se.erase({xl, xr, xv});
    //debug(xv, xr - xl + 1);
    if (xv > 0) {
      upd(xv, -(xr - xl + 1));      
    }
  }
  for (auto [xl, xr, xv] : psh) {
    if (xv > 0) {
      upd(xv, xr - xl + 1);       
    }
    se.insert({xl, xr, xv});
  }
}

void upd(int u, int v, int val) {
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) {
      swap(u, v); 
    }
    ins(id[top[u]], id[u], val);
    u = pr[top[u]];
  }
  if (dep[u] < dep[v]) {
    swap(u, v);
  }
  ins(id[v], id[u], val);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m, q;
  cin >> n >> m >> q;
  for(int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 1);
  dfs_hld(1, 1, 1);
  se.insert({1, n, 0});
  for (int i = 1; i <= m; ++i) {
    cin >> c[i]; 
  }
  for (int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;
    qs[r].push_back({l, i});
  }
  for (int r = 2; r <= m; ++r) {
    upd(c[r - 1], c[r], r - 1);
    upd(c[r], c[r], r); 
    for (auto [ql, qi] : qs[r]) {
      ans[qi] = qry(ql, r); 
    }
  }
  for (int i = 0; i < q; ++i) {
    cout << ans[i] << '\n';
  }
  return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Incorrect 204 ms 10580 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 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 5184 KB Output is correct
4 Incorrect 488 ms 15188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

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