oj.uz

Submission #518361

# Submission time Handle Problem Language Result Execution time Memory
518361 2022-01-23T14:25:03 Z Alex_tz307 Regions (IOI09_regions) C++17
100 / 100
 2690 ms 35652 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> large, g[kN], R[kR], nodes[kR];
vector<pair<int, int>> subtrees[kR];
bitset<kN> isLarge;

void dfs(int u) {
  in[u] = ++timer;
  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]) {
    dfs(v);
  }
  if (isLarge[r[u]]) {
    --cnt[ind[r[u]]];
  }
  out[u] = timer;
}

int query(int r1, int r2) {
  int ans = 0, ptr = 0, cover = 0;
  for (int curr : nodes[r2]) {
    while (ptr < (int)subtrees[r1].size() && subtrees[r1][ptr].first <= curr) {
      cover += subtrees[r1][ptr].second;
      ptr += 1;
    }
    ans += cover;
  }
  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);
    } else {
      int u;
      cin >> u >> r[v];
      r[v] -= 1;
      g[u - 1].emplace_back(v);
      R[r[v]].emplace_back(v);
    }
  }
  for (int i = 0; i < m; ++i) {
    if ((int)R[i].size() > kBuck) {
      isLarge[i] = true;
      ind[i] = large.size();
      large.emplace_back(i);
    }
  }
  dfs(0);
  for (int i = 0; i < m; ++i) {
    for (int v : R[i]) {
      subtrees[i].emplace_back(in[v], 1);
      subtrees[i].emplace_back(out[v] + 1, -1);
      nodes[i].emplace_back(in[v]);
    }
    sort(subtrees[i].begin(), subtrees[i].end());
    sort(nodes[i].begin(), nodes[i].end());
  }
  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 << query(r1, r2) << '\n';
    cout.flush();
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6728 KB Output is correct
2 Correct 4 ms 6728 KB Output is correct
3 Correct 6 ms 6728 KB Output is correct
4 Correct 5 ms 6728 KB Output is correct
5 Correct 11 ms 6728 KB Output is correct
6 Correct 21 ms 6856 KB Output is correct
7 Correct 39 ms 6856 KB Output is correct
8 Correct 35 ms 6856 KB Output is correct
9 Correct 57 ms 7368 KB Output is correct
10 Correct 97 ms 7496 KB Output is correct
11 Correct 87 ms 7880 KB Output is correct
12 Correct 125 ms 8520 KB Output is correct
13 Correct 152 ms 8292 KB Output is correct
14 Correct 204 ms 9184 KB Output is correct
15 Correct 146 ms 12068 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 13404 KB Output is correct
2 Correct 870 ms 12312 KB Output is correct
3 Correct 1293 ms 15508 KB Output is correct
4 Correct 213 ms 9152 KB Output is correct
5 Correct 359 ms 10812 KB Output is correct
6 Correct 650 ms 14648 KB Output is correct
7 Correct 1092 ms 13684 KB Output is correct
8 Correct 1120 ms 26696 KB Output is correct
9 Correct 1577 ms 19984 KB Output is correct
10 Correct 2238 ms 35652 KB Output is correct
11 Correct 2521 ms 20364 KB Output is correct
12 Correct 1014 ms 22112 KB Output is correct
13 Correct 1244 ms 22396 KB Output is correct
14 Correct 1196 ms 26052 KB Output is correct
15 Correct 2232 ms 27104 KB Output is correct
16 Correct 2690 ms 31988 KB Output is correct
17 Correct 2315 ms 34768 KB Output is correct