oj.uz

Submission #415250

# Submission time Handle Problem Language Result Execution time Memory
415250 2021-05-31T18:12:08 Z Alex_tz307 Regions (IOI09_regions) C++17
100 / 100
 5693 ms 44784 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5;
const int MAXR = 25 * 1e3;
const int BLOCK = 450;
int m, r[MAXN], timer, in[MAXN], out[MAXN], cnt_large, ind[MAXR], root[BLOCK][MAXR];
vector<int> G[MAXN], R[MAXR], pos[MAXR];
bitset<MAXN> is_large;
map<int,int> 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) {
  for (auto it : large)
    root[it.first][r[u]] += it.second;
  if (is_large[r[u]])
    ++large[ind[r[u]]];
  for (int v : G[u])
    dfs2(v);
  if (is_large[r[u]])
    --large[ind[r[u]]];
}

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++;
    }
  dfs2(0);
  map<pair<int,int>,int> sol;
  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 {
      pair<int,int> p{r1, r2};
      auto it = sol.find(p);
      if (it != sol.end())
        cout << it->second << '\n';
      else {
        int ans = solve(r1, r2);
        sol[p] = ans;
        cout << ans << '\n';
      }
    }
    cout.flush();
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6088 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 6 ms 6088 KB Output is correct
4 Correct 11 ms 6216 KB Output is correct
5 Correct 13 ms 6216 KB Output is correct
6 Correct 22 ms 6380 KB Output is correct
7 Correct 38 ms 6404 KB Output is correct
8 Correct 38 ms 6464 KB Output is correct
9 Correct 64 ms 7104 KB Output is correct
10 Correct 141 ms 7084 KB Output is correct
11 Correct 185 ms 7488 KB Output is correct
12 Correct 179 ms 8336 KB Output is correct
13 Correct 247 ms 7900 KB Output is correct
14 Correct 402 ms 8540 KB Output is correct
15 Correct 409 ms 13052 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1472 ms 13088 KB Output is correct
2 Correct 1783 ms 11420 KB Output is correct
3 Correct 2293 ms 18376 KB Output is correct
4 Correct 314 ms 9376 KB Output is correct
5 Correct 325 ms 12672 KB Output is correct
6 Correct 585 ms 13168 KB Output is correct
7 Correct 1273 ms 12360 KB Output is correct
8 Correct 1452 ms 25528 KB Output is correct
9 Correct 3020 ms 24716 KB Output is correct
10 Correct 4431 ms 38020 KB Output is correct
11 Correct 5693 ms 27460 KB Output is correct
12 Correct 1749 ms 20928 KB Output is correct
13 Correct 2312 ms 23628 KB Output is correct
14 Correct 3589 ms 25488 KB Output is correct
15 Correct 4370 ms 34044 KB Output is correct
16 Correct 4156 ms 44784 KB Output is correct
17 Correct 4146 ms 43820 KB Output is correct