oj.uz

Submission #415234

# Submission time Handle Problem Language Result Execution time Memory
415234 2021-05-31T17:36:50 Z Alex_tz307 Regions (IOI09_regions) C++17
75 / 100
 8000 ms 33936 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5;
const int MAXR = 25 * 1e3;
const int BLOCK = 445;
int m, r[MAXN], timer, in[MAXN], out[MAXN], cnt_large, ind[MAXR], dp[MAXR], root[BLOCK][MAXR], child[BLOCK][MAXR];
vector<int> G[MAXN], R[MAXR], pos[MAXR], S;
bitset<MAXN> is_large;

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, int region) {
  if (r[u] == region)
    for (int i = 0; i < m; ++i)
      child[ind[region]][i] += dp[i];
  ++dp[r[u]];
  for (int v : G[u])
    dfs2(v, region);
  --dp[r[u]];
}

void dfs3(int u) {
  for (int region : S)
    ++root[ind[region]][r[u]];
  if (is_large[r[u]])
    S.emplace_back(r[u]);
  for (int v : G[u])
    dfs3(v);
  if (is_large[r[u]])
    S.pop_back();
}

int solve(int r1, int r2) {
  int ans = 0;
  for (int u : R[r1]) {
    int n = pos[r2].size();
    int st = n, dr = n, l = 0, r = n - 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (in[u] <= pos[r2][mid]) {
        st = mid;
        r = mid - 1;
      } else l = mid + 1;
    }
    l = 0, r = n - 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (out[u] < pos[r2][mid]) {
        dr = mid;
        r = mid - 1;
      } else l = mid + 1;
    }
    ans += dr - st;
  }
  return ans;
}

int main() {
  int n, 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) {
      is_large[i] = true;
      ind[i] = cnt_large++;
      for (int j = 0; j < m; ++j)
        dp[j] = 0;
      dfs2(0, i);
    }
  dfs3(0);
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    cin >> r1 >> r2;
    --r1, --r2;
    if ((int)R[r1].size() > BLOCK)
      cout << root[ind[r1]][r2] << '\n';
    else if ((int)R[r2].size() > BLOCK)
      cout << child[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 6088 KB Output is correct
2 Correct 5 ms 6088 KB Output is correct
3 Correct 8 ms 6088 KB Output is correct
4 Correct 9 ms 6088 KB Output is correct
5 Correct 11 ms 6216 KB Output is correct
6 Correct 20 ms 6216 KB Output is correct
7 Correct 21 ms 6216 KB Output is correct
8 Correct 41 ms 6216 KB Output is correct
9 Correct 80 ms 6636 KB Output is correct
10 Correct 94 ms 6716 KB Output is correct
11 Correct 194 ms 6984 KB Output is correct
12 Correct 166 ms 7480 KB Output is correct
13 Correct 212 ms 7100 KB Output is correct
14 Correct 392 ms 7784 KB Output is correct
15 Correct 411 ms 10304 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3272 ms 11356 KB Output is correct
2 Correct 1931 ms 9824 KB Output is correct
3 Correct 7582 ms 13484 KB Output is correct
4 Correct 429 ms 7788 KB Output is correct
5 Correct 293 ms 9408 KB Output is correct
6 Correct 1627 ms 13148 KB Output is correct
7 Correct 2083 ms 11848 KB Output is correct
8 Execution timed out 8019 ms 25400 KB Time limit exceeded
9 Correct 3164 ms 15512 KB Output is correct
10 Execution timed out 8029 ms 33936 KB Time limit exceeded
11 Correct 5447 ms 15444 KB Output is correct
12 Correct 2634 ms 17216 KB Output is correct
13 Correct 4725 ms 17844 KB Output is correct
14 Correct 5784 ms 20876 KB Output is correct
15 Execution timed out 8007 ms 22800 KB Time limit exceeded
16 Execution timed out 8032 ms 30316 KB Time limit exceeded
17 Execution timed out 8082 ms 32236 KB Time limit exceeded