oj.uz

Submission #518345

# Submission time Handle Problem Language Result Execution time Memory
518345 2022-01-23T13:18:08 Z Alex_tz307 Regions (IOI09_regions) C++17
100 / 100
 4497 ms 31504 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 + 1], 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 4 ms 6088 KB Output is correct
3 Correct 7 ms 6088 KB Output is correct
4 Correct 9 ms 6088 KB Output is correct
5 Correct 12 ms 6088 KB Output is correct
6 Correct 25 ms 6216 KB Output is correct
7 Correct 40 ms 6216 KB Output is correct
8 Correct 39 ms 6216 KB Output is correct
9 Correct 47 ms 6600 KB Output is correct
10 Correct 91 ms 6716 KB Output is correct
11 Correct 132 ms 6996 KB Output is correct
12 Correct 172 ms 7524 KB Output is correct
13 Correct 239 ms 7188 KB Output is correct
14 Correct 335 ms 7752 KB Output is correct
15 Correct 289 ms 10312 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1089 ms 11200 KB Output is correct
2 Correct 1642 ms 10000 KB Output is correct
3 Correct 2057 ms 12984 KB Output is correct
4 Correct 315 ms 7876 KB Output is correct
5 Correct 413 ms 9336 KB Output is correct
6 Correct 673 ms 12984 KB Output is correct
7 Correct 1527 ms 11564 KB Output is correct
8 Correct 891 ms 24128 KB Output is correct
9 Correct 2513 ms 15600 KB Output is correct
10 Correct 3509 ms 31504 KB Output is correct
11 Correct 4497 ms 15440 KB Output is correct
12 Correct 1470 ms 17856 KB Output is correct
13 Correct 2215 ms 17988 KB Output is correct
14 Correct 2001 ms 21356 KB Output is correct
15 Correct 3183 ms 22484 KB Output is correct
16 Correct 2673 ms 27736 KB Output is correct
17 Correct 2444 ms 29960 KB Output is correct