oj.uz

Submission #518349

# Submission time Handle Problem Language Result Execution time Memory
518349 2022-01-23T13:32:30 Z Alex_tz307 Regions (IOI09_regions) C++17
100 / 100
 4697 ms 31492 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 query(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);
    } else {
      int u;
      cin >> u >> r[v];
      r[v] -= 1;
      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 << query(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 5 ms 6088 KB Output is correct
4 Correct 8 ms 6088 KB Output is correct
5 Correct 12 ms 6216 KB Output is correct
6 Correct 23 ms 6216 KB Output is correct
7 Correct 34 ms 6184 KB Output is correct
8 Correct 28 ms 6256 KB Output is correct
9 Correct 53 ms 6732 KB Output is correct
10 Correct 90 ms 6628 KB Output is correct
11 Correct 131 ms 6984 KB Output is correct
12 Correct 182 ms 7520 KB Output is correct
13 Correct 221 ms 7112 KB Output is correct
14 Correct 305 ms 7756 KB Output is correct
15 Correct 298 ms 10232 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1387 ms 11164 KB Output is correct
2 Correct 1434 ms 10056 KB Output is correct
3 Correct 2276 ms 12992 KB Output is correct
4 Correct 283 ms 7768 KB Output is correct
5 Correct 410 ms 9376 KB Output is correct
6 Correct 664 ms 13120 KB Output is correct
7 Correct 1295 ms 11552 KB Output is correct
8 Correct 928 ms 24128 KB Output is correct
9 Correct 2552 ms 15508 KB Output is correct
10 Correct 2980 ms 31492 KB Output is correct
11 Correct 4697 ms 15348 KB Output is correct
12 Correct 1546 ms 17748 KB Output is correct
13 Correct 2188 ms 17984 KB Output is correct
14 Correct 1866 ms 21360 KB Output is correct
15 Correct 3610 ms 22480 KB Output is correct
16 Correct 2950 ms 27828 KB Output is correct
17 Correct 2782 ms 29976 KB Output is correct