oj.uz

Submission #518348

# Submission time Handle Problem Language Result Execution time Memory
518348 2022-01-23T13:27:15 Z Alex_tz307 Regions (IOI09_regions) C++17
100 / 100
 4529 ms 31504 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 2e5;
const int kR = 25 * 1e3;
const int kBuck = 450;
int timer, r[kN], in[kN], out[kN], ind[kR], cnt[kBuck], sum[1 + kN], root1[kBuck][kR], root2[kBuck][kR];
vector<int> g[kN], R[kR], pos[kR], large;
bitset<kN> isLarge;

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 (int region : large) {
    root1[ind[region]][r[u]] += cnt[ind[region]];
  }
  if (isLarge[r[u]]) {
    ++cnt[ind[r[u]]];
  }
  for (int v : g[u]) {
    dfs2(v);
  }
  if (isLarge[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() > kBuck) {
      isLarge[i] = true;
      ind[i] = large.size();
      large.emplace_back(i);
    }
  }
  dfs2(0);
  for (int r2 : large) {
    for (int v : R[r2]) {
      sum[in[v]] += 1;
    }
    for (int i = 1; i <= n; ++i) {
      sum[i] += sum[i - 1];
    }
    for (int v = 0; v < n; ++v) {
      root2[ind[r2]][r[v]] += sum[out[v]] - sum[in[v] - 1];
    }
    for (int i = 1; i <= n; ++i) {
      sum[i] = 0;
    }
  }
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    cin >> r1 >> r2;
    r1 -= 1, r2 -= 1;
    if ((int)R[r1].size() > kBuck) {
      cout << root1[ind[r1]][r2] << '\n';
    } else if ((int)R[r2].size() > kBuck) {
      cout << root2[ind[r2]][r1] << '\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 3 ms 6088 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 4 ms 6088 KB Output is correct
4 Correct 8 ms 6088 KB Output is correct
5 Correct 9 ms 6216 KB Output is correct
6 Correct 14 ms 6268 KB Output is correct
7 Correct 42 ms 6216 KB Output is correct
8 Correct 42 ms 6344 KB Output is correct
9 Correct 45 ms 6784 KB Output is correct
10 Correct 88 ms 6728 KB Output is correct
11 Correct 150 ms 6984 KB Output is correct
12 Correct 160 ms 7496 KB Output is correct
13 Correct 197 ms 7112 KB Output is correct
14 Correct 325 ms 7752 KB Output is correct
15 Correct 352 ms 10312 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1428 ms 11188 KB Output is correct
2 Correct 1413 ms 9988 KB Output is correct
3 Correct 3042 ms 13000 KB Output is correct
4 Correct 244 ms 7864 KB Output is correct
5 Correct 454 ms 9368 KB Output is correct
6 Correct 987 ms 13096 KB Output is correct
7 Correct 1738 ms 11480 KB Output is correct
8 Correct 1067 ms 24204 KB Output is correct
9 Correct 2651 ms 15540 KB Output is correct
10 Correct 2809 ms 31504 KB Output is correct
11 Correct 4529 ms 15456 KB Output is correct
12 Correct 1740 ms 17804 KB Output is correct
13 Correct 1883 ms 18008 KB Output is correct
14 Correct 2342 ms 21356 KB Output is correct
15 Correct 3463 ms 22480 KB Output is correct
16 Correct 3244 ms 27692 KB Output is correct
17 Correct 2756 ms 29892 KB Output is correct