oj.uz

Submission #518360

# Submission time Handle Problem Language Result Execution time Memory
518360 2022-01-23T14:22:07 Z Alex_tz307 Regions (IOI09_regions) C++17
100 / 100
 2587 ms 35748 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];
bitset<kN> isLarge;
vector<pair<int, int>> subtrees[kR];
vector<int> nodes[kR];

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 4 ms 6728 KB Output is correct
2 Correct 5 ms 6728 KB Output is correct
3 Correct 7 ms 6728 KB Output is correct
4 Correct 6 ms 6728 KB Output is correct
5 Correct 11 ms 6728 KB Output is correct
6 Correct 22 ms 6856 KB Output is correct
7 Correct 27 ms 6856 KB Output is correct
8 Correct 39 ms 6856 KB Output is correct
9 Correct 65 ms 7368 KB Output is correct
10 Correct 86 ms 7496 KB Output is correct
11 Correct 133 ms 7824 KB Output is correct
12 Correct 110 ms 8448 KB Output is correct
13 Correct 171 ms 8276 KB Output is correct
14 Correct 148 ms 9288 KB Output is correct
15 Correct 199 ms 11976 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 13408 KB Output is correct
2 Correct 980 ms 12324 KB Output is correct
3 Correct 1395 ms 15504 KB Output is correct
4 Correct 268 ms 9072 KB Output is correct
5 Correct 353 ms 10728 KB Output is correct
6 Correct 596 ms 14628 KB Output is correct
7 Correct 912 ms 13636 KB Output is correct
8 Correct 981 ms 26776 KB Output is correct
9 Correct 1498 ms 20132 KB Output is correct
10 Correct 1943 ms 35748 KB Output is correct
11 Correct 2587 ms 20396 KB Output is correct
12 Correct 995 ms 22088 KB Output is correct
13 Correct 1202 ms 22396 KB Output is correct
14 Correct 1464 ms 26060 KB Output is correct
15 Correct 2117 ms 27100 KB Output is correct
16 Correct 2227 ms 31980 KB Output is correct
17 Correct 2062 ms 34768 KB Output is correct