oj.uz

Submission #518346

# Submission time Handle Problem Language Result Execution time Memory
518346 2022-01-23T13:20:42 Z Alex_tz307 Regions (IOI09_regions) C++17
100 / 100
 4649 ms 31396 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], sum[1 + MAXN], root1[BLOCK][MAXR], root2[BLOCK][MAXR];
vector<int> g[MAXN], R[MAXR], pos[MAXR], large;
bitset<MAXN> 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 (auto 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() > BLOCK) {
      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, --r2;
    if ((int)R[r1].size() > BLOCK) {
      cout << root1[ind[r1]][r2] << '\n';
    } else if ((int)R[r2].size() > BLOCK) {
      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 3 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 6 ms 6088 KB Output is correct
6 Correct 24 ms 6224 KB Output is correct
7 Correct 34 ms 6216 KB Output is correct
8 Correct 40 ms 6216 KB Output is correct
9 Correct 74 ms 6728 KB Output is correct
10 Correct 93 ms 6676 KB Output is correct
11 Correct 129 ms 6984 KB Output is correct
12 Correct 168 ms 7424 KB Output is correct
13 Correct 205 ms 7176 KB Output is correct
14 Correct 323 ms 7888 KB Output is correct
15 Correct 347 ms 10288 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1385 ms 11180 KB Output is correct
2 Correct 1443 ms 10196 KB Output is correct
3 Correct 2563 ms 13024 KB Output is correct
4 Correct 361 ms 7824 KB Output is correct
5 Correct 369 ms 9356 KB Output is correct
6 Correct 667 ms 13044 KB Output is correct
7 Correct 1610 ms 11460 KB Output is correct
8 Correct 1053 ms 24168 KB Output is correct
9 Correct 2658 ms 15704 KB Output is correct
10 Correct 3022 ms 31396 KB Output is correct
11 Correct 4649 ms 15440 KB Output is correct
12 Correct 1343 ms 17760 KB Output is correct
13 Correct 2168 ms 18036 KB Output is correct
14 Correct 2333 ms 21360 KB Output is correct
15 Correct 3449 ms 22484 KB Output is correct
16 Correct 3301 ms 27692 KB Output is correct
17 Correct 2887 ms 29980 KB Output is correct