oj.uz

Submission #415252

# Submission time Handle Problem Language Result Execution time Memory
415252 2021-05-31T18:19:19 Z Alex_tz307 Regions (IOI09_regions) C++17
100 / 100
 5109 ms 27328 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5;
const int MAXR = 25 * 1e3;
const int BLOCK = 450;
int r[MAXN], timer, in[MAXN], out[MAXN], cnt_large, ind[MAXR], root[BLOCK][MAXR];
vector<int> G[MAXN], R[MAXR], pos[MAXR];
bitset<MAXN> is_large;
unordered_map<int,int> large;

void dfs1(int u) {
  in[u] = ++timer;
  pos[r[u]].emplace_back(in[u]);
  for (int v : G[u])
    dfs1(v);
  out[u] = timer;
}

void dfs2(int u) {
  for (auto it : large)
    root[it.first][r[u]] += it.second;
  if (is_large[r[u]])
    ++large[ind[r[u]]];
  for (int v : G[u])
    dfs2(v);
  if (is_large[r[u]])
    --large[ind[r[u]]];
}

int solve(int r1, int r2) {
  int ans = 0;
  for (int u : R[r1]) {
    int n = pos[r2].size();
    int st = n, dr = n, l = 0, r = n - 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (in[u] <= pos[r2][mid]) {
        st = mid;
        r = mid - 1;
      } else l = mid + 1;
    }
    l = 0, r = n - 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (out[u] < pos[r2][mid]) {
        dr = mid;
        r = mid - 1;
      } else l = mid + 1;
    }
    ans += dr - st;
  }
  return ans;
}

int main() {
  int n, m, Q;
  cin >> n >> m >> Q;
  for (int v = 0; v < n; ++v) {
    if (v == 0) {
      cin >> r[0];
      --r[0];
      R[r[0]].emplace_back(0);
      continue;
    }
    int u;
    cin >> u >> r[v];
    --r[v];
    G[u - 1].emplace_back(v);
    R[r[v]].emplace_back(v);
  }
  dfs1(0);
  for (int i = 0; i < m; ++i)
    if ((int)R[i].size() > BLOCK) {
      is_large[i] = true;
      ind[i] = cnt_large++;
    }
  dfs2(0);
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    cin >> r1 >> r2;
    --r1, --r2;
    if ((int)R[r1].size() > BLOCK)
      cout << root[ind[r1]][r2] << '\n';
    else cout << solve(r1, r2) << '\n';
    cout.flush();
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6088 KB Output is correct
2 Correct 5 ms 6088 KB Output is correct
3 Correct 8 ms 6088 KB Output is correct
4 Correct 11 ms 6088 KB Output is correct
5 Correct 15 ms 6088 KB Output is correct
6 Correct 25 ms 6216 KB Output is correct
7 Correct 37 ms 6216 KB Output is correct
8 Correct 48 ms 6216 KB Output is correct
9 Correct 35 ms 6600 KB Output is correct
10 Correct 109 ms 6728 KB Output is correct
11 Correct 138 ms 7020 KB Output is correct
12 Correct 122 ms 7496 KB Output is correct
13 Correct 280 ms 7108 KB Output is correct
14 Correct 347 ms 7752 KB Output is correct
15 Correct 354 ms 10304 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2041 ms 10856 KB Output is correct
2 Correct 2748 ms 9664 KB Output is correct
3 Correct 3373 ms 12608 KB Output is correct
4 Correct 312 ms 7744 KB Output is correct
5 Correct 609 ms 9416 KB Output is correct
6 Correct 687 ms 10944 KB Output is correct
7 Correct 2131 ms 10668 KB Output is correct
8 Correct 1381 ms 19392 KB Output is correct
9 Correct 3461 ms 15552 KB Output is correct
10 Correct 4021 ms 25688 KB Output is correct
11 Correct 5109 ms 15356 KB Output is correct
12 Correct 1673 ms 16940 KB Output is correct
13 Correct 2327 ms 17128 KB Output is correct
14 Correct 2956 ms 18764 KB Output is correct
15 Correct 4405 ms 21568 KB Output is correct
16 Correct 3332 ms 26900 KB Output is correct
17 Correct 3556 ms 27328 KB Output is correct