oj.uz

Submission #952842

# Submission time Handle Problem Language Result Execution time Memory
952842 2024-03-25T02:23:57 Z kilkuwu Regions (IOI09_regions) C++17
95 / 100
 3634 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 = 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 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 3 ms 344 KB Output is correct
6 Correct 8 ms 624 KB Output is correct
7 Correct 15 ms 600 KB Output is correct
8 Correct 14 ms 732 KB Output is correct
9 Correct 23 ms 1368 KB Output is correct
10 Correct 57 ms 1832 KB Output is correct
11 Correct 67 ms 2516 KB Output is correct
12 Correct 90 ms 3548 KB Output is correct
13 Correct 111 ms 3672 KB Output is correct
14 Correct 213 ms 4424 KB Output is correct
15 Correct 237 ms 8456 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 11664 KB Output is correct
2 Correct 912 ms 10772 KB Output is correct
3 Correct 1840 ms 15184 KB Output is correct
4 Correct 153 ms 6832 KB Output is correct
5 Correct 262 ms 10716 KB Output is correct
6 Correct 325 ms 14892 KB Output is correct
7 Correct 803 ms 23948 KB Output is correct
8 Correct 601 ms 38244 KB Output is correct
9 Correct 1593 ms 65740 KB Output is correct
10 Correct 1560 ms 113332 KB Output is correct
11 Correct 3634 ms 123356 KB Output is correct
12 Correct 1026 ms 86292 KB Output is correct
13 Correct 1540 ms 86732 KB Output is correct
14 Correct 1411 ms 105916 KB Output is correct
15 Correct 2458 ms 130752 KB Output is correct
16 Runtime error 108 ms 131072 KB Execution killed with signal 9
17 Correct 1977 ms 116920 KB Output is correct