oj.uz

Submission #518344

# Submission time Handle Problem Language Result Execution time Memory
518344 2022-01-23T13:16:49 Z Alex_tz307 Regions (IOI09_regions) C++17
35 / 100
 5164 ms 57316 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[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 5 ms 6164 KB Output is correct
2 Correct 3 ms 6088 KB Output is correct
3 Correct 6 ms 6140 KB Output is correct
4 Correct 7 ms 6088 KB Output is correct
5 Correct 9 ms 6088 KB Output is correct
6 Correct 20 ms 6216 KB Output is correct
7 Correct 28 ms 6216 KB Output is correct
8 Correct 39 ms 6304 KB Output is correct
9 Correct 56 ms 6728 KB Output is correct
10 Correct 84 ms 6636 KB Output is correct
11 Correct 157 ms 6984 KB Output is correct
12 Correct 171 ms 7444 KB Output is correct
13 Correct 235 ms 7096 KB Output is correct
14 Correct 333 ms 7728 KB Output is correct
15 Correct 282 ms 10304 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1274 ms 11200 KB Output isn't correct
2 Incorrect 1505 ms 10152 KB Output isn't correct
3 Incorrect 2525 ms 13004 KB Output isn't correct
4 Correct 262 ms 7792 KB Output is correct
5 Correct 340 ms 9360 KB Output is correct
6 Runtime error 80 ms 22784 KB Execution killed with signal 11
7 Runtime error 75 ms 22144 KB Execution killed with signal 11
8 Runtime error 182 ms 41096 KB Execution killed with signal 11
9 Correct 2661 ms 15620 KB Output is correct
10 Runtime error 239 ms 53316 KB Execution killed with signal 11
11 Correct 5164 ms 15376 KB Output is correct
12 Runtime error 189 ms 35688 KB Execution killed with signal 11
13 Runtime error 216 ms 36136 KB Execution killed with signal 11
14 Runtime error 241 ms 39700 KB Execution killed with signal 11
15 Runtime error 221 ms 44944 KB Execution killed with signal 11
16 Runtime error 201 ms 55688 KB Execution killed with signal 11
17 Runtime error 256 ms 57316 KB Execution killed with signal 11