oj.uz

Submission #415253

# Submission time Handle Problem Language Result Execution time Memory
415253 2021-05-31T18:24:11 Z Alex_tz307 Regions (IOI09_regions) C++17
100 / 100
 4933 ms 27184 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], ind[MAXR], cnt[BLOCK], root[BLOCK][MAXR];
vector<int> G[MAXN], R[MAXR], pos[MAXR], large;
bitset<MAXN> is_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 region : large)
    root[ind[region]][r[u]] += cnt[ind[region]];
  if (is_large[r[u]])
    ++cnt[ind[r[u]]];
  for (int v : G[u])
    dfs2(v);
  if (is_large[r[u]])
    --cnt[ind[r[u]]];
}

int solve(int r1, int r2) {
  int ans = 0;
  for (int u : R[r1]) {
    int st = lower_bound(pos[r2].begin(), pos[r2].end(), in[u]) - pos[r2].begin();
    int dr = upper_bound(pos[r2].begin(), pos[r2].end(), out[u]) - pos[r2].begin();
    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] = large.size();
      large.emplace_back(i);
    }
  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 4 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 9 ms 6088 KB Output is correct
5 Correct 11 ms 6216 KB Output is correct
6 Correct 22 ms 6216 KB Output is correct
7 Correct 37 ms 6216 KB Output is correct
8 Correct 55 ms 6216 KB Output is correct
9 Correct 51 ms 6600 KB Output is correct
10 Correct 133 ms 6728 KB Output is correct
11 Correct 151 ms 6984 KB Output is correct
12 Correct 146 ms 7496 KB Output is correct
13 Correct 205 ms 7112 KB Output is correct
14 Correct 386 ms 7720 KB Output is correct
15 Correct 397 ms 10304 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2041 ms 10784 KB Output is correct
2 Correct 2519 ms 9668 KB Output is correct
3 Correct 3118 ms 12556 KB Output is correct
4 Correct 321 ms 7748 KB Output is correct
5 Correct 600 ms 9380 KB Output is correct
6 Correct 598 ms 11072 KB Output is correct
7 Correct 2021 ms 10668 KB Output is correct
8 Correct 1453 ms 19452 KB Output is correct
9 Correct 3560 ms 15552 KB Output is correct
10 Correct 3994 ms 25708 KB Output is correct
11 Correct 4933 ms 15344 KB Output is correct
12 Correct 2112 ms 16956 KB Output is correct
13 Correct 2538 ms 17088 KB Output is correct
14 Correct 3255 ms 18752 KB Output is correct
15 Correct 3881 ms 21492 KB Output is correct
16 Correct 3990 ms 26840 KB Output is correct
17 Correct 4161 ms 27184 KB Output is correct