oj.uz

Submission #1000909

# Submission time Handle Problem Language Result Execution time Memory
1000909 2024-06-18T11:11:55 Z LucaLucaM Tourism (JOI23_tourism) C++17
10 / 100
 82 ms 56612 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <set>
#warning That's the baby, that's not my baby

#define debug(x) #x << " = " << x << '\n'

typedef long long ll;

const int NMAX = 1e5;
const int LGMAX = 16;

int aib[NMAX + 1];
int answer[NMAX + 1];

int a[NMAX + 1];

std::vector<int> g[NMAX + 1];
std::set<std::pair<int, int>> queries[NMAX + 1];
std::vector<std::pair<int, int>> curQ[NMAX + 1];

int depth[NMAX + 1];
int tin[NMAX + 1], tout[NMAX + 1], timer;

int jump[LGMAX + 1][NMAX + 1];

int sum[NMAX + 1];
int added[NMAX + 1], added2[NMAX + 1];
int parent[NMAX + 1];

bool ancestor(int u, int v) {
  return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
  if (ancestor(u, v)) {
    return u;
  }
  for (int k = LGMAX; k >= 0; k--) {
    if (jump[k][u] != 0 && !ancestor(jump[k][u], v)) {
      u = jump[k][u];
    }
  }
  return jump[0][u];
}

void dfs(int u, int p = 0) {
  depth[u] = depth[p] + 1;
  tin[u] = ++timer;
  jump[0][u] = p;
  for (const auto &v : g[u]) {
    if (v != p) {
      dfs(v, u);
    }
  }
  tout[u] = ++timer;
}

void dfs1(int u) {
  for (const auto &v : g[u]) {
    if (v != parent[u]) {
      parent[v] = u;
      dfs1(v);
    }
  }
}

std::vector<std::pair<int, int>> updates;

void update(int pos, const int &val) {
  updates.push_back({pos, val});
  for (; pos <= NMAX; pos += pos & -pos) {
    aib[pos] += val;
  }
}

int query(int pos) {
  int ret = 0;
  for (; pos > 0; pos -= pos & -pos) {
    ret += aib[pos];
  }
  return ret;
}

void divide(int l, int r) {
  if (l >= r) {
    return;
  }
  int mid = (l + r) / 2;
  for (int i = mid + 1; i <= r; i++) {
    auto st = queries[i].lower_bound({l, 0});
    auto it = st;
    while (it != queries[i].end() && it -> first <= mid) {
      curQ[i].push_back(*it);
      it = next(it);
    }
    for (const auto &[L, index] : curQ[i]) {
      queries[i].erase({L, index});
    }
  }


  std::vector<int> vert;
  for (int i = l; i <= r; i++) {
    vert.push_back(a[i]);
  }
  std::sort(vert.begin(), vert.end(), [&](int x, int y) {
    return tin[x] < tin[y];
  });
  vert.erase(std::unique(vert.begin(), vert.end()), vert.end());
  int sz = (int) vert.size();
  for (int i = 1; i < sz; i++) {
    vert.push_back(lca(vert[i - 1], vert[i]));
  }
  std::sort(vert.begin(), vert.end(), [&](int x, int y) {
    return tin[x] < tin[y];
  });
  vert.erase(std::unique(vert.begin(), vert.end()), vert.end());
  for (int i = 1; i < (int) vert.size(); i++) {
    int w = lca(vert[i - 1], vert[i]);
    g[w].push_back(vert[i]);
    g[vert[i]].push_back(w);
  }
//  if (l == 1 && r == 3) {
//    std::cout << "? " << (int) curQ[3].size() << '\n';
//    for (const auto &u : vert) {
//      std::cout << u << ' ';
//    }
//    std::cout << "\n\n";
//  }
  for (const auto &u : vert) {
    parent[u] = 0;
  }
  dfs1(a[mid]);
  for (const auto &u : vert) {
    added[u] = added2[u] = 0;
  }
  sum[mid] = 0;
  added[a[mid]] = added2[a[mid]] = mid;

  for (int i = mid - 1; i >= l; i--) {
    int u = a[i];
    int add = 0;
    while (!added[u]) {
      added[u] = i;
      add += std::abs(depth[u] - depth[parent[u]]);
      u = parent[u];
    }
    sum[i] = sum[i + 1] + add;
  }

  for (int i = mid + 1; i <= r; i++) {
    int u = a[i];
    while (!added2[u]) {
      if (added[u] != mid) {
        update(added[u] + 1, std::abs(depth[u] - depth[parent[u]]));
      }
      added2[u] = i;
      u = parent[u];
    }
    for (const auto &[L, index] : curQ[i]) {
      answer[index] = query(L) + sum[L];
    }
    curQ[i].clear();
  }

  for (const auto &[x, y] : updates) {
    update(x, -y);
  }
  updates.clear();
  for (const auto &u : vert) {
    g[u].clear();
  }

  if (l < r) {
    divide(l, mid);
    divide(mid + 1, r);
  }
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n, m, q;
  std::cin >> n >> m >> q;

  for (int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  dfs(1);

  for (int k = 1; k <= LGMAX; k++) {
    for (int i = 1; i <= n; i++) {
      jump[k][i] = jump[k - 1][jump[k - 1][i]];
    }
  }

  for (int i = 1; i <= m; i++) {
    std::cin >> a[i];
  }

  for (int i = 0; i < q; i++) {
    int l, r;
    std::cin >> l >> r;
    if (l != r) {
      queries[r].insert({l, i});
    } else {
      answer[i] = 0;
    }
  }

  for (int i = 1; i <= n; i++) {
    g[i].clear();
  }

  divide(1, m);

//  std::cout << "\n\nMy debug:\n\n";
//  for (int i = 1; i <= n; i++) {
//    std::cout << depth[i] << ' ';
//  }
//  std::cout << '\n';
//
//  std::cout << "\n\nYour queries:\n\n";

  for (int i = 0; i < q; i++) {
    std::cout << answer[i] + 1 << '\n';
  }

  return 0;
}

Compilation message

tourism.cpp:7:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    7 | #warning That's the baby, that's not my baby
      |  ^~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 2 ms 16988 KB Output is correct
6 Correct 2 ms 17128 KB Output is correct
7 Correct 2 ms 17128 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 3 ms 16984 KB Output is correct
13 Correct 3 ms 17076 KB Output is correct
14 Correct 3 ms 17132 KB Output is correct
15 Correct 4 ms 17028 KB Output is correct
16 Correct 2 ms 16988 KB Output is correct
17 Correct 2 ms 16988 KB Output is correct
18 Correct 3 ms 16984 KB Output is correct
19 Correct 3 ms 16988 KB Output is correct
20 Correct 3 ms 16988 KB Output is correct
21 Correct 3 ms 16988 KB Output is correct
22 Correct 3 ms 17044 KB Output is correct
23 Correct 3 ms 16988 KB Output is correct
24 Correct 2 ms 16988 KB Output is correct
25 Correct 3 ms 16984 KB Output is correct
26 Correct 2 ms 16988 KB Output is correct
27 Correct 2 ms 16988 KB Output is correct
28 Correct 2 ms 16988 KB Output is correct
29 Correct 3 ms 16984 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 2 ms 16988 KB Output is correct
6 Correct 2 ms 17128 KB Output is correct
7 Correct 2 ms 17128 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 3 ms 16984 KB Output is correct
13 Correct 3 ms 17076 KB Output is correct
14 Correct 3 ms 17132 KB Output is correct
15 Correct 4 ms 17028 KB Output is correct
16 Correct 2 ms 16988 KB Output is correct
17 Correct 2 ms 16988 KB Output is correct
18 Correct 3 ms 16984 KB Output is correct
19 Correct 3 ms 16988 KB Output is correct
20 Correct 3 ms 16988 KB Output is correct
21 Correct 3 ms 16988 KB Output is correct
22 Correct 3 ms 17044 KB Output is correct
23 Correct 3 ms 16988 KB Output is correct
24 Correct 2 ms 16988 KB Output is correct
25 Correct 3 ms 16984 KB Output is correct
26 Correct 2 ms 16988 KB Output is correct
27 Correct 2 ms 16988 KB Output is correct
28 Correct 2 ms 16988 KB Output is correct
29 Correct 3 ms 16984 KB Output is correct
30 Correct 7 ms 17244 KB Output is correct
31 Correct 7 ms 17244 KB Output is correct
32 Correct 8 ms 17244 KB Output is correct
33 Correct 8 ms 17244 KB Output is correct
34 Correct 10 ms 17244 KB Output is correct
35 Correct 7 ms 17244 KB Output is correct
36 Correct 8 ms 17244 KB Output is correct
37 Correct 8 ms 17244 KB Output is correct
38 Correct 7 ms 17244 KB Output is correct
39 Correct 6 ms 17464 KB Output is correct
40 Correct 7 ms 17240 KB Output is correct
41 Correct 6 ms 17244 KB Output is correct
42 Correct 6 ms 17244 KB Output is correct
43 Correct 7 ms 17244 KB Output is correct
44 Correct 7 ms 17240 KB Output is correct
45 Correct 7 ms 17424 KB Output is correct
46 Correct 8 ms 17244 KB Output is correct
47 Correct 8 ms 17388 KB Output is correct
48 Correct 7 ms 17244 KB Output is correct
49 Correct 8 ms 17244 KB Output is correct
50 Correct 6 ms 17244 KB Output is correct
51 Correct 6 ms 17388 KB Output is correct
52 Correct 6 ms 17244 KB Output is correct
53 Correct 6 ms 17244 KB Output is correct
54 Correct 6 ms 17432 KB Output is correct
55 Correct 6 ms 17244 KB Output is correct
56 Correct 3 ms 16988 KB Output is correct
57 Correct 4 ms 16988 KB Output is correct
58 Correct 8 ms 17240 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 3 ms 16980 KB Output is correct
4 Runtime error 71 ms 56612 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16984 KB Output is correct
2 Runtime error 44 ms 42600 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 16984 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Runtime error 82 ms 53584 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 2 ms 16988 KB Output is correct
6 Correct 2 ms 17128 KB Output is correct
7 Correct 2 ms 17128 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 3 ms 16984 KB Output is correct
13 Correct 3 ms 17076 KB Output is correct
14 Correct 3 ms 17132 KB Output is correct
15 Correct 4 ms 17028 KB Output is correct
16 Correct 2 ms 16988 KB Output is correct
17 Correct 2 ms 16988 KB Output is correct
18 Correct 3 ms 16984 KB Output is correct
19 Correct 3 ms 16988 KB Output is correct
20 Correct 3 ms 16988 KB Output is correct
21 Correct 3 ms 16988 KB Output is correct
22 Correct 3 ms 17044 KB Output is correct
23 Correct 3 ms 16988 KB Output is correct
24 Correct 2 ms 16988 KB Output is correct
25 Correct 3 ms 16984 KB Output is correct
26 Correct 2 ms 16988 KB Output is correct
27 Correct 2 ms 16988 KB Output is correct
28 Correct 2 ms 16988 KB Output is correct
29 Correct 3 ms 16984 KB Output is correct
30 Correct 7 ms 17244 KB Output is correct
31 Correct 7 ms 17244 KB Output is correct
32 Correct 8 ms 17244 KB Output is correct
33 Correct 8 ms 17244 KB Output is correct
34 Correct 10 ms 17244 KB Output is correct
35 Correct 7 ms 17244 KB Output is correct
36 Correct 8 ms 17244 KB Output is correct
37 Correct 8 ms 17244 KB Output is correct
38 Correct 7 ms 17244 KB Output is correct
39 Correct 6 ms 17464 KB Output is correct
40 Correct 7 ms 17240 KB Output is correct
41 Correct 6 ms 17244 KB Output is correct
42 Correct 6 ms 17244 KB Output is correct
43 Correct 7 ms 17244 KB Output is correct
44 Correct 7 ms 17240 KB Output is correct
45 Correct 7 ms 17424 KB Output is correct
46 Correct 8 ms 17244 KB Output is correct
47 Correct 8 ms 17388 KB Output is correct
48 Correct 7 ms 17244 KB Output is correct
49 Correct 8 ms 17244 KB Output is correct
50 Correct 6 ms 17244 KB Output is correct
51 Correct 6 ms 17388 KB Output is correct
52 Correct 6 ms 17244 KB Output is correct
53 Correct 6 ms 17244 KB Output is correct
54 Correct 6 ms 17432 KB Output is correct
55 Correct 6 ms 17244 KB Output is correct
56 Correct 3 ms 16988 KB Output is correct
57 Correct 4 ms 16988 KB Output is correct
58 Correct 8 ms 17240 KB Output is correct
59 Correct 2 ms 16988 KB Output is correct
60 Correct 2 ms 16988 KB Output is correct
61 Correct 3 ms 16980 KB Output is correct
62 Runtime error 71 ms 56612 KB Execution killed with signal 11
63 Halted 0 ms 0 KB -