oj.uz

Submission #952844

# Submission time Handle Problem Language Result Execution time Memory
952844 2024-03-25T02:37:04 Z kilkuwu Regions (IOI09_regions) C++17
100 / 100
 2894 ms 127224 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);
  int ti = 0;

  std::function<void(int)> dfs = [&](int u) -> void {
    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>> b1((n - 1) / BLOCK_SIZE + 1, std::vector<int>(r));
  std::vector<std::vector<int>> b2((n - 1) / BLOCK_SIZE + 1, std::vector<int>(r));
  std::vector<int> map_block(r, -1);
  std::vector<int> dp(n);

  int bid = 0;
  for (int x = 0; x < r; x++) {
    if (homes[x].size() >= BLOCK_SIZE) {
      map_block[x] = bid;

      std::fill(dp.begin(), dp.end(), 0);

      for (int u : homes[x]) dp[u] = 1;

      for (int i = 0; i < n; i++) {
        if (i > 0) dp[i] += dp[pa[i]]; // dp[i] = number of us that is parent of this
        b1[bid][home[i]] += dp[i];
      }

      std::fill(dp.begin(), dp.end(), 0);

      for (int u : homes[x]) dp[u] = 1;

      for (int i = n - 1; i >= 0; i--) {
        if (i > 0) dp[pa[i]] += dp[i]; // dp[i] = number of us that this is parent
        b2[bid][home[i]] += dp[i]; // con den cha
      }
      
      bid++;
    }
  }

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

    if (map_block[a] != -1) {
      // how can i do the reverse?
      std::cout << b1[map_block[a]][b] << std::endl;
      continue;
    } 

    if (map_block[b] != -1) {
      std::cout << b2[map_block[b]][a] << 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 1 ms 596 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 3 ms 344 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 14 ms 344 KB Output is correct
8 Correct 17 ms 600 KB Output is correct
9 Correct 27 ms 1112 KB Output is correct
10 Correct 51 ms 1272 KB Output is correct
11 Correct 77 ms 1764 KB Output is correct
12 Correct 97 ms 2536 KB Output is correct
13 Correct 112 ms 2224 KB Output is correct
14 Correct 177 ms 2904 KB Output is correct
15 Correct 222 ms 6408 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 7552 KB Output is correct
2 Correct 797 ms 6392 KB Output is correct
3 Correct 1833 ms 10244 KB Output is correct
4 Correct 165 ms 5300 KB Output is correct
5 Correct 221 ms 8832 KB Output is correct
6 Correct 374 ms 12024 KB Output is correct
7 Correct 807 ms 20096 KB Output is correct
8 Correct 580 ms 32740 KB Output is correct
9 Correct 1620 ms 58108 KB Output is correct
10 Correct 1494 ms 104008 KB Output is correct
11 Correct 2894 ms 112988 KB Output is correct
12 Correct 896 ms 75872 KB Output is correct
13 Correct 1327 ms 76304 KB Output is correct
14 Correct 1268 ms 94952 KB Output is correct
15 Correct 2298 ms 119792 KB Output is correct
16 Correct 2300 ms 127224 KB Output is correct
17 Correct 1964 ms 105948 KB Output is correct