oj.uz

Submission #1107614

# Submission time Handle Problem Language Result Execution time Memory
1107614 2024-11-01T17:15:35 Z abczz Tourism (JOI23_tourism) C++17
18 / 100
 210 ms 54344 KB 
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#define ll long long

using namespace std;

vector <ll> adj[100000];
vector <array<ll, 2>> Q[100000];
ll bl[100000][18];
ll n, m, q, a, b, cnt, sz[100000], A[100000], D[100000], G[100000], pos[100000], X[100000];
vector <ll> V[100000];

ll tot = 0;
struct BIT{
  ll st[100050];
  void build(){
    memset(st, 0, sizeof(st));
  }
  void update(ll id, ll w) {
    if (!id) return;
    tot += w;
    for (; id<100050; id+=id&-id) st[id] += w;
  }
  ll query(ll id) {
    ll ret = 0;
    for (; id; id-=id&-id) ret += st[id];
    return ret;
  }
}bit;
struct MPSegment{
  map <ll, array<ll, 2>> mp;
  vector <ll> lazy;
  void init(ll sz) {
    mp[0] = {sz-1, -1};
  }
  void update(ll id, ll l, ll r, ll w) {
    auto it = mp.lower_bound(l);
    if (it != mp.begin()) {
      it = prev(it);
      bit.update(it->second[1]+1, -(it->second[0]-(l-1)));
      mp[it->first] = {l-1, it->second[1]};
    }
    it = mp.lower_bound(l);
    while (it != mp.end()) {
      auto nx = next(it);
      if (it->first > r) break;
      if (it->second[0] <= r) {
        bit.update(it->second[1]+1, -(it->second[0]-it->first+1));
        mp.erase(it);
      }
      else {
        bit.update(it->second[1]+1, -(r+1-it->first));
        mp[r+1] = {it->second[0], it->second[1]};
        mp.erase(it);
        break;
      }
      it = nx;
    }
    mp[l] = {r, w};
    bit.update(w+1, r-l+1);
  }
}ST[100000];
ll lca(ll a, ll b) {
  if (a == -1) return b;
  else if (b == -1) return a;
  if (D[a] > D[b]) swap(a, b);
  ll db = D[b];
  for (int j=17; j>=0; --j) {
    if (db-(1LL<<j) >= D[a]) {
      db -= (1LL<<j);
      b = bl[b][j];
    }
  }
  for (int j=17; j>=0; --j) {
    if (bl[a][j] != bl[b][j]) {
      a = bl[a][j], b = bl[b][j];
    }
  }
  if (a != b) return bl[a][0];
  else return a;
}
struct LCATree{
  ll st[400000];
  void build(ll id, ll l, ll r) {
    if (l == r) {
      st[id] = lca(A[l], A[l+1]);
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    st[id] = lca(st[id*2], st[id*2+1]);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return -1;
    else if (ql <= l && r <= qr) return st[id];
    ll mid = (l+r)/2;
    return lca(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
  }
}LCAST;
void dfs(ll u, ll p) {
  sz[u] = 1;
  for (auto v : adj[u]) {
    if (v == p) continue;
    D[v] = D[u] + 1;
    bl[v][0] = u;
    sz[u] += sz[v];
    dfs(v, u);
  }
}
void hld(ll u, ll p, ll k) {
  G[u] = k, pos[u] = V[k].size();
  V[k].push_back(u);
  ll mx = -1, id = -1;
  for (auto v : adj[u]) {
    if (v == p) continue;
    if (sz[v] > mx) mx = sz[v], id = v;
  }
  if (id != -1) hld(id, u, k);
  for (auto v : adj[u]) {
    if (v == p || v == id) continue;
    X[cnt+1] = u;
    hld(v, u, ++cnt);
  }
}
void jump(ll u, ll v, ll w) {
  if (G[u] == G[v]) {
    if (pos[v] == pos[u]) return;
    ST[G[u]].update(1, pos[v], pos[u], w);
    return;
  }
  ST[G[u]].update(1, 0, pos[u], w);
  jump(X[G[u]], v, w);
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m >> q;
  bit.build();
  for (int i=0; i<n-1; ++i) {
    cin >> a >> b;
    --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dfs(0, -1);
  hld(0, -1, 0);
  for (int j=1; j<18; ++j) {
    for (int i=0; i<n; ++i) {
      bl[i][j] = bl[bl[i][j-1]][j-1];
    }
  }
  for (int i=0; i<=cnt; ++i) {
    ST[i].init(V[i].size());
  }
  vector <ll> F(q, 0);
  for (int i=0; i<m; ++i) {
    cin >> A[i];
    --A[i];
  }
  if (m > 1) LCAST.build(1, 0, m-2);
  for (int i=0; i<q; ++i) {
    cin >> a >> b;
    --a, --b;
    Q[b].push_back({a, i});
  }
  for (int i=0; i<m; ++i) {
    jump(A[i], 0, i);
    for (auto [x, y] : Q[i]) {
      if (x == i) {
        F[y] = 1;
        continue;
      }
      F[y] = tot - bit.query(x) - (m == 1 ? 0 : D[LCAST.query(1, 0, m-2, x, i-1)]);
      //cout << tot << " " << bit.query(x) << endl;
    }
  }
  for (int i=0; i<q; ++i) cout << F[i] << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20560 KB Output is correct
2 Correct 5 ms 20560 KB Output is correct
3 Correct 5 ms 20560 KB Output is correct
4 Correct 5 ms 20560 KB Output is correct
5 Correct 5 ms 20560 KB Output is correct
6 Correct 5 ms 20560 KB Output is correct
7 Correct 5 ms 20560 KB Output is correct
8 Correct 6 ms 20560 KB Output is correct
9 Correct 5 ms 20560 KB Output is correct
10 Correct 6 ms 20680 KB Output is correct
11 Correct 5 ms 20628 KB Output is correct
12 Correct 5 ms 20560 KB Output is correct
13 Correct 5 ms 20560 KB Output is correct
14 Correct 5 ms 20616 KB Output is correct
15 Incorrect 5 ms 20560 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20560 KB Output is correct
2 Correct 5 ms 20560 KB Output is correct
3 Correct 5 ms 20560 KB Output is correct
4 Correct 5 ms 20560 KB Output is correct
5 Correct 5 ms 20560 KB Output is correct
6 Correct 5 ms 20560 KB Output is correct
7 Correct 5 ms 20560 KB Output is correct
8 Correct 6 ms 20560 KB Output is correct
9 Correct 5 ms 20560 KB Output is correct
10 Correct 6 ms 20680 KB Output is correct
11 Correct 5 ms 20628 KB Output is correct
12 Correct 5 ms 20560 KB Output is correct
13 Correct 5 ms 20560 KB Output is correct
14 Correct 5 ms 20616 KB Output is correct
15 Incorrect 5 ms 20560 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20640 KB Output is correct
2 Correct 100 ms 38560 KB Output is correct
3 Correct 136 ms 39492 KB Output is correct
4 Correct 106 ms 42568 KB Output is correct
5 Correct 170 ms 49036 KB Output is correct
6 Correct 165 ms 49092 KB Output is correct
7 Correct 162 ms 48968 KB Output is correct
8 Correct 166 ms 48972 KB Output is correct
9 Correct 166 ms 49000 KB Output is correct
10 Correct 163 ms 49144 KB Output is correct
11 Correct 172 ms 49168 KB Output is correct
12 Correct 170 ms 49128 KB Output is correct
13 Correct 175 ms 49736 KB Output is correct
14 Correct 181 ms 50628 KB Output is correct
15 Correct 198 ms 54344 KB Output is correct
16 Correct 184 ms 49736 KB Output is correct
17 Correct 210 ms 49508 KB Output is correct
18 Correct 205 ms 49716 KB Output is correct
19 Correct 164 ms 43696 KB Output is correct
20 Correct 152 ms 43688 KB Output is correct
21 Correct 150 ms 43592 KB Output is correct
22 Correct 153 ms 43592 KB Output is correct
23 Correct 160 ms 43544 KB Output is correct
24 Correct 153 ms 43600 KB Output is correct
25 Correct 177 ms 43740 KB Output is correct
26 Correct 150 ms 43724 KB Output is correct
27 Correct 160 ms 43592 KB Output is correct
28 Correct 158 ms 43592 KB Output is correct
29 Correct 169 ms 43668 KB Output is correct
30 Correct 163 ms 43848 KB Output is correct
31 Correct 202 ms 44164 KB Output is correct
32 Correct 198 ms 44872 KB Output is correct
33 Correct 183 ms 46280 KB Output is correct
34 Correct 177 ms 48892 KB Output is correct

Subtask #5
0 / 24.0

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

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20560 KB Output is correct
2 Correct 5 ms 20560 KB Output is correct
3 Correct 5 ms 20560 KB Output is correct
4 Correct 5 ms 20560 KB Output is correct
5 Correct 5 ms 20560 KB Output is correct
6 Correct 5 ms 20560 KB Output is correct
7 Correct 5 ms 20560 KB Output is correct
8 Correct 6 ms 20560 KB Output is correct
9 Correct 5 ms 20560 KB Output is correct
10 Correct 6 ms 20680 KB Output is correct
11 Correct 5 ms 20628 KB Output is correct
12 Correct 5 ms 20560 KB Output is correct
13 Correct 5 ms 20560 KB Output is correct
14 Correct 5 ms 20616 KB Output is correct
15 Incorrect 5 ms 20560 KB Output isn't correct
16 Halted 0 ms 0 KB -