oj.uz

Submission #952843

# Submission time Handle Problem Language Result Execution time Memory
952843 2024-03-25T02:34:31 Z kilkuwu Regions (IOI09_regions) C++17
100 / 100
 2951 ms 128004 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>> 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);

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

      std::vector<int> dp(n);
      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 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 3 ms 344 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 12 ms 344 KB Output is correct
8 Correct 14 ms 600 KB Output is correct
9 Correct 19 ms 1112 KB Output is correct
10 Correct 38 ms 1112 KB Output is correct
11 Correct 77 ms 1756 KB Output is correct
12 Correct 86 ms 2536 KB Output is correct
13 Correct 108 ms 2212 KB Output is correct
14 Correct 168 ms 2760 KB Output is correct
15 Correct 227 ms 6404 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 7856 KB Output is correct
2 Correct 813 ms 6696 KB Output is correct
3 Correct 1719 ms 10596 KB Output is correct
4 Correct 194 ms 5304 KB Output is correct
5 Correct 215 ms 8836 KB Output is correct
6 Correct 320 ms 12232 KB Output is correct
7 Correct 810 ms 20572 KB Output is correct
8 Correct 552 ms 33144 KB Output is correct
9 Correct 1644 ms 58108 KB Output is correct
10 Correct 1460 ms 104672 KB Output is correct
11 Correct 2951 ms 112992 KB Output is correct
12 Correct 853 ms 76612 KB Output is correct
13 Correct 1291 ms 77044 KB Output is correct
14 Correct 1222 ms 95740 KB Output is correct
15 Correct 2403 ms 120572 KB Output is correct
16 Correct 2302 ms 128004 KB Output is correct
17 Correct 2041 ms 106736 KB Output is correct