oj.uz

Submission #1030769

# Submission time Handle Problem Language Result Execution time Memory
1030769 2024-07-22T09:46:53 Z NeroZein Tourism (JOI23_tourism) C++17
24 / 100
 893 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]});
    }
  }
  //debug(l, r, val, pp, psh);
  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);
  }
  //assert(id[v] <= id[u]);
  //debug(u, v, id[v], id[u]);
  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 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 3 ms 5264 KB Output is correct
10 Correct 3 ms 5104 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 3 ms 5172 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 5208 KB Output is correct
16 Correct 2 ms 5216 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 3 ms 5212 KB Output is correct
19 Correct 3 ms 5208 KB Output is correct
20 Correct 3 ms 5212 KB Output is correct
21 Correct 3 ms 5212 KB Output is correct
22 Correct 2 ms 5212 KB Output is correct
23 Correct 3 ms 5268 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct
25 Correct 4 ms 5212 KB Output is correct
26 Correct 3 ms 5208 KB Output is correct
27 Correct 3 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 2 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 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 3 ms 5264 KB Output is correct
10 Correct 3 ms 5104 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 3 ms 5172 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 5208 KB Output is correct
16 Correct 2 ms 5216 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 3 ms 5212 KB Output is correct
19 Correct 3 ms 5208 KB Output is correct
20 Correct 3 ms 5212 KB Output is correct
21 Correct 3 ms 5212 KB Output is correct
22 Correct 2 ms 5212 KB Output is correct
23 Correct 3 ms 5268 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct
25 Correct 4 ms 5212 KB Output is correct
26 Correct 3 ms 5208 KB Output is correct
27 Correct 3 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 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 107 ms 17236 KB Output is correct
5 Correct 83 ms 19792 KB Output is correct
6 Correct 105 ms 21504 KB Output is correct
7 Correct 130 ms 24656 KB Output is correct
8 Correct 133 ms 24548 KB Output is correct
9 Correct 134 ms 24548 KB Output is correct
10 Correct 143 ms 24660 KB Output is correct
11 Correct 131 ms 24632 KB Output is correct
12 Correct 140 ms 24144 KB Output is correct
13 Correct 150 ms 24120 KB Output is correct
14 Correct 158 ms 24144 KB Output is correct
15 Incorrect 36 ms 20704 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 5212 KB Output is correct
2 Correct 282 ms 11572 KB Output is correct
3 Correct 435 ms 12804 KB Output is correct
4 Correct 336 ms 13308 KB Output is correct
5 Correct 524 ms 16980 KB Output is correct
6 Correct 547 ms 17056 KB Output is correct
7 Correct 534 ms 16996 KB Output is correct
8 Correct 504 ms 16976 KB Output is correct
9 Correct 554 ms 16980 KB Output is correct
10 Correct 548 ms 17028 KB Output is correct
11 Correct 567 ms 16960 KB Output is correct
12 Correct 534 ms 17204 KB Output is correct
13 Correct 534 ms 17448 KB Output is correct
14 Correct 540 ms 18512 KB Output is correct
15 Incorrect 576 ms 21748 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 731 ms 16456 KB Output is correct
5 Correct 685 ms 16432 KB Output is correct
6 Correct 786 ms 19792 KB Output is correct
7 Correct 826 ms 21536 KB Output is correct
8 Correct 819 ms 21584 KB Output is correct
9 Correct 817 ms 21404 KB Output is correct
10 Correct 821 ms 21544 KB Output is correct
11 Correct 796 ms 21584 KB Output is correct
12 Correct 814 ms 21584 KB Output is correct
13 Correct 893 ms 21488 KB Output is correct
14 Correct 47 ms 9808 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 3 ms 5264 KB Output is correct
10 Correct 3 ms 5104 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 3 ms 5172 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 5208 KB Output is correct
16 Correct 2 ms 5216 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 3 ms 5212 KB Output is correct
19 Correct 3 ms 5208 KB Output is correct
20 Correct 3 ms 5212 KB Output is correct
21 Correct 3 ms 5212 KB Output is correct
22 Correct 2 ms 5212 KB Output is correct
23 Correct 3 ms 5268 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct
25 Correct 4 ms 5212 KB Output is correct
26 Correct 3 ms 5208 KB Output is correct
27 Correct 3 ms 5212 KB Output is correct
28 Incorrect 2 ms 5212 KB Output isn't correct
29 Halted 0 ms 0 KB -