oj.uz

Submission #952835

# Submission time Handle Problem Language Result Execution time Memory
952835 2024-03-25T02:09:38 Z kilkuwu Regions (IOI09_regions) C++17
100 / 100
 3504 ms 89524 KB 
#include <bits/stdc++.h>


#define nl '\n'

#ifdef LOCAL
#include "template\debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, r, q;
  std::cin >> n >> r >> q;
  std::vector<int> home(n), pa(n);
  std::vector<std::vector<int>> adj(n);
  std::vector<std::vector<int>> homes(r);
  std::cin >> home[0];
  --home[0];
  homes[home[0]].push_back(0);
  for (int i = 1; i < n; i++) {
    std::cin >> pa[i] >> home[i];
    adj[--pa[i]].push_back(i);
    --home[i];
    homes[home[i]].push_back(i);
  }

  std::vector<int> st(n), en(n), who(n);
  int ti = 0;

  std::function<void(int)> dfs = [&](int u) -> void {
    who[ti] = u;
    st[u] = ti++;
    for (int v : adj[u]) {
      dfs(v);
    }
    en[u] = ti;
  };


  dfs(0);

  for (int i = 0; i < r; i++) {
    std::sort(homes[i].begin(), homes[i].end(), [&](int u, int v) {
      return st[u] < st[v];
    });
  }

  constexpr int BLOCK_SIZE = 400;

  std::vector<std::vector<int>> blocks((n - 1) / BLOCK_SIZE + 1, std::vector<int>(r));
  std::vector<int> map_block(n, -1);
  std::vector<std::map<int, int>> mp(n);

  int bid = 0;
  for (int x = 0; x < r; x++) {
    if (homes[x].size() >= BLOCK_SIZE) {
      map_block[x] = bid;
      std::vector<int> t(n + 1);

      for (int u : homes[x]) {
        t[st[u]]++;
        t[en[u]]--;
      }

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

      for (int i = 0; i < n; i++) {
        blocks[bid][home[who[i]]] += t[i];
      }

      bid++;
    }
  }

  while (q--) {
    int a, b;
    std::cin >> a >> b;
    --a, --b;

    if (map_block[a] != -1) {
      std::cout << blocks[map_block[a]][b] << std::endl;
      continue;
    } 

    int ans = 0;
    for (int u : homes[a]) {
      int f = std::lower_bound(homes[b].begin(), homes[b].end(), st[u], [&](int x, int y) {
        return st[x] < y;
      }) - homes[b].begin();
      int e = std::lower_bound(homes[b].begin(), homes[b].end(), en[u], [&](int x, int y) {
        return st[x] < y;
      }) - homes[b].begin();

      ans += e - f;
    }

    std::cout << ans << std::endl;
  }
}      

/*

homes[1] = {1, 6}
homes[2] = {2}
homes[3] = {3, 4, 5}

*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 7 ms 620 KB Output is correct
7 Correct 12 ms 600 KB Output is correct
8 Correct 14 ms 744 KB Output is correct
9 Correct 23 ms 1368 KB Output is correct
10 Correct 46 ms 1792 KB Output is correct
11 Correct 73 ms 2484 KB Output is correct
12 Correct 91 ms 3460 KB Output is correct
13 Correct 101 ms 3564 KB Output is correct
14 Correct 185 ms 4364 KB Output is correct
15 Correct 223 ms 8352 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1577 ms 11520 KB Output is correct
2 Correct 1847 ms 10592 KB Output is correct
3 Correct 2397 ms 14944 KB Output is correct
4 Correct 150 ms 5668 KB Output is correct
5 Correct 215 ms 8916 KB Output is correct
6 Correct 363 ms 11316 KB Output is correct
7 Correct 1035 ms 17108 KB Output is correct
8 Correct 734 ms 28652 KB Output is correct
9 Correct 1708 ms 43712 KB Output is correct
10 Correct 2305 ms 71728 KB Output is correct
11 Correct 3504 ms 74220 KB Output is correct
12 Correct 977 ms 56528 KB Output is correct
13 Correct 1392 ms 56956 KB Output is correct
14 Correct 1487 ms 66760 KB Output is correct
15 Correct 2354 ms 81804 KB Output is correct
16 Correct 2378 ms 89524 KB Output is correct
17 Correct 2337 ms 77800 KB Output is correct