oj.uz

Submission #952839

# Submission time Handle Problem Language Result Execution time Memory
952839 2024-03-25T02:21:13 Z kilkuwu Regions (IOI09_regions) C++17
95 / 100
 2822 ms 131072 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(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;

      // propagate down

      std::vector<int> dp(n);
      for (int u : homes[x]) dp[u] = 1;

      for (int i = 1; i < n; i++) {
        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 344 KB Output is correct
2 Correct 0 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 12 ms 600 KB Output is correct
7 Correct 16 ms 608 KB Output is correct
8 Correct 14 ms 740 KB Output is correct
9 Correct 23 ms 1368 KB Output is correct
10 Correct 48 ms 1876 KB Output is correct
11 Correct 68 ms 2520 KB Output is correct
12 Correct 81 ms 3548 KB Output is correct
13 Correct 109 ms 3428 KB Output is correct
14 Correct 166 ms 4576 KB Output is correct
15 Correct 217 ms 8460 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 11664 KB Output is correct
2 Correct 917 ms 10788 KB Output is correct
3 Correct 1856 ms 15172 KB Output is correct
4 Correct 183 ms 6832 KB Output is correct
5 Correct 258 ms 10720 KB Output is correct
6 Correct 326 ms 14880 KB Output is correct
7 Correct 835 ms 23960 KB Output is correct
8 Correct 639 ms 38236 KB Output is correct
9 Correct 1651 ms 65764 KB Output is correct
10 Correct 1295 ms 113324 KB Output is correct
11 Correct 2822 ms 123164 KB Output is correct
12 Correct 858 ms 86280 KB Output is correct
13 Correct 1296 ms 86720 KB Output is correct
14 Correct 1240 ms 106048 KB Output is correct
15 Correct 2325 ms 130760 KB Output is correct
16 Runtime error 103 ms 131072 KB Execution killed with signal 9
17 Correct 2082 ms 116920 KB Output is correct