oj.uz

Submission #1030773

# Submission time Handle Problem Language Result Execution time Memory
1030773 2024-07-22T09:50:05 Z NeroZein Tourism (JOI23_tourism) C++17
24 / 100
 948 ms 24660 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]});
    } 
    if ((*itr)[1] > r) {
      psh.push_back({r + 1, (*itr)[1], (*itr)[2]});
    }
  }
  itr++;
  while (itr != se.end() && (*itr)[0] <= r) {
    pp.push_back(*itr);
    if ((*itr)[1] > r) {
      psh.push_back({r + 1, (*itr)[1], (*itr)[2]});
    }
    itr++;
  }
  for (auto [xl, xr, xv] : pp) {
    if (xv > 0) {
      upd(xv, -(xr - xl + 1));      
    }
    se.erase({xl, xr, xv});
  }
  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});
  }
  upd(c[1], c[1], 1);
  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 3 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 3 ms 5168 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 2 ms 5172 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 3 ms 5212 KB Output is correct
15 Correct 3 ms 5212 KB Output is correct
16 Correct 4 ms 5212 KB Output is correct
17 Correct 3 ms 5212 KB Output is correct
18 Correct 3 ms 5212 KB Output is correct
19 Correct 3 ms 5212 KB Output is correct
20 Correct 3 ms 5208 KB Output is correct
21 Correct 3 ms 5208 KB Output is correct
22 Correct 3 ms 5212 KB Output is correct
23 Correct 3 ms 5212 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct
25 Correct 2 ms 5212 KB Output is correct
26 Correct 2 ms 5176 KB Output is correct
27 Correct 2 ms 5212 KB Output is correct
28 Incorrect 2 ms 5212 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 3 ms 5168 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 2 ms 5172 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 3 ms 5212 KB Output is correct
15 Correct 3 ms 5212 KB Output is correct
16 Correct 4 ms 5212 KB Output is correct
17 Correct 3 ms 5212 KB Output is correct
18 Correct 3 ms 5212 KB Output is correct
19 Correct 3 ms 5212 KB Output is correct
20 Correct 3 ms 5208 KB Output is correct
21 Correct 3 ms 5208 KB Output is correct
22 Correct 3 ms 5212 KB Output is correct
23 Correct 3 ms 5212 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct
25 Correct 2 ms 5212 KB Output is correct
26 Correct 2 ms 5176 KB Output is correct
27 Correct 2 ms 5212 KB Output is correct
28 Incorrect 2 ms 5212 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5164 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 116 ms 17116 KB Output is correct
5 Correct 80 ms 19744 KB Output is correct
6 Correct 107 ms 21584 KB Output is correct
7 Correct 149 ms 24656 KB Output is correct
8 Correct 151 ms 24552 KB Output is correct
9 Correct 133 ms 24572 KB Output is correct
10 Correct 142 ms 24660 KB Output is correct
11 Correct 140 ms 24656 KB Output is correct
12 Correct 153 ms 24144 KB Output is correct
13 Correct 142 ms 24148 KB Output is correct
14 Correct 147 ms 24016 KB Output is correct
15 Incorrect 36 ms 20692 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 289 ms 11616 KB Output is correct
3 Correct 435 ms 12880 KB Output is correct
4 Correct 333 ms 13116 KB Output is correct
5 Correct 533 ms 17232 KB Output is correct
6 Correct 558 ms 16976 KB Output is correct
7 Correct 488 ms 16952 KB Output is correct
8 Correct 540 ms 16724 KB Output is correct
9 Correct 515 ms 16724 KB Output is correct
10 Correct 575 ms 16724 KB Output is correct
11 Correct 516 ms 16976 KB Output is correct
12 Correct 561 ms 17128 KB Output is correct
13 Correct 558 ms 17492 KB Output is correct
14 Correct 548 ms 18532 KB Output is correct
15 Incorrect 535 ms 21764 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
24.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 5212 KB Output is correct
4 Correct 721 ms 16492 KB Output is correct
5 Correct 680 ms 16584 KB Output is correct
6 Correct 764 ms 19800 KB Output is correct
7 Correct 807 ms 21492 KB Output is correct
8 Correct 877 ms 21484 KB Output is correct
9 Correct 830 ms 21104 KB Output is correct
10 Correct 922 ms 21172 KB Output is correct
11 Correct 924 ms 21564 KB Output is correct
12 Correct 936 ms 21428 KB Output is correct
13 Correct 948 ms 21612 KB Output is correct
14 Correct 54 ms 9636 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 3 ms 5168 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 2 ms 5172 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 3 ms 5212 KB Output is correct
15 Correct 3 ms 5212 KB Output is correct
16 Correct 4 ms 5212 KB Output is correct
17 Correct 3 ms 5212 KB Output is correct
18 Correct 3 ms 5212 KB Output is correct
19 Correct 3 ms 5212 KB Output is correct
20 Correct 3 ms 5208 KB Output is correct
21 Correct 3 ms 5208 KB Output is correct
22 Correct 3 ms 5212 KB Output is correct
23 Correct 3 ms 5212 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct
25 Correct 2 ms 5212 KB Output is correct
26 Correct 2 ms 5176 KB Output is correct
27 Correct 2 ms 5212 KB Output is correct
28 Incorrect 2 ms 5212 KB Output isn't correct
29 Halted 0 ms 0 KB -