oj.uz

Submission #415251

# Submission time Handle Problem Language Result Execution time Memory
415251 2021-05-31T18:17:05 Z Alex_tz307 Regions (IOI09_regions) C++17
100 / 100
 5888 ms 35764 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;
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 6 ms 6088 KB Output is correct
3 Correct 7 ms 6088 KB Output is correct
4 Correct 12 ms 6088 KB Output is correct
5 Correct 14 ms 6216 KB Output is correct
6 Correct 21 ms 6216 KB Output is correct
7 Correct 43 ms 6216 KB Output is correct
8 Correct 40 ms 6216 KB Output is correct
9 Correct 79 ms 6908 KB Output is correct
10 Correct 110 ms 6728 KB Output is correct
11 Correct 196 ms 6984 KB Output is correct
12 Correct 196 ms 7624 KB Output is correct
13 Correct 267 ms 7292 KB Output is correct
14 Correct 354 ms 7744 KB Output is correct
15 Correct 329 ms 12096 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2213 ms 11584 KB Output is correct
2 Correct 2797 ms 9792 KB Output is correct
3 Correct 3606 ms 14272 KB Output is correct
4 Correct 321 ms 7880 KB Output is correct
5 Correct 465 ms 10604 KB Output is correct
6 Correct 865 ms 11192 KB Output is correct
7 Correct 2129 ms 10840 KB Output is correct
8 Correct 1314 ms 22680 KB Output is correct
9 Correct 2827 ms 16448 KB Output is correct
10 Correct 4442 ms 29888 KB Output is correct
11 Correct 5888 ms 15608 KB Output is correct
12 Correct 1933 ms 17188 KB Output is correct
13 Correct 2366 ms 17984 KB Output is correct
14 Correct 2503 ms 19108 KB Output is correct
15 Correct 4256 ms 24736 KB Output is correct
16 Correct 3465 ms 35764 KB Output is correct
17 Correct 3894 ms 34948 KB Output is correct