oj.uz

Submission #415180

# Submission time Handle Problem Language Result Execution time Memory
415180 2021-05-31T16:07:31 Z Alex_tz307 Regions (IOI09_regions) C++17
80 / 100
 8000 ms 34824 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5;
const int MAXR = 25 * 1e3;
int r[MAXN], timer, in[MAXN], out[MAXN];
vector<int> G[MAXN], R[MAXR], pos[MAXR];

void dfs(int u) {
  in[u] = ++timer;
  pos[r[u]].emplace_back(in[u]);
  for (int v : G[u])
    dfs(v);
  out[u] = timer;
}

int solve(int r1, int r2) {
  int ans = 0;
  for (int u : R[r1]) {
    int n = pos[r2].size(), st, dr, step, aux;
    for (step = 1; step < n; step <<= 1);
    aux = step;
    for (st = 0; step; step >>= 1) {
      int ind = st | step;
      if (ind <= n && pos[r2][ind - 1] < in[u])
        st |= step;
    }
    step = aux;
    for (dr = 0; step; step >>= 1) {
      int ind = dr | step;
      if (ind <= n && pos[r2][ind - 1] <= out[u])
        dr |= step;
    }
    ans += dr - st;
  }
  return ans;
}

int main() {
  int n, Q;
  cin >> n >> Q >> 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);
  }
  dfs(0);
  map<pair<int,int>,int> sol;
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    cin >> r1 >> r2;
    --r1, --r2;
    pair<int,int> p{r1, r2};
    auto it = sol.find(p);
    if (it != sol.end())
      cout << it->second << endl;
    else {
      int ans = solve(r1, r2);
      sol[p] = ans;
      cout << ans << endl;
    }
  }
  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 6 ms 6084 KB Output is correct
3 Correct 8 ms 6184 KB Output is correct
4 Correct 12 ms 6184 KB Output is correct
5 Correct 16 ms 6216 KB Output is correct
6 Correct 28 ms 6424 KB Output is correct
7 Correct 52 ms 6336 KB Output is correct
8 Correct 39 ms 6432 KB Output is correct
9 Correct 73 ms 6900 KB Output is correct
10 Correct 121 ms 7048 KB Output is correct
11 Correct 171 ms 7704 KB Output is correct
12 Correct 229 ms 8060 KB Output is correct
13 Correct 271 ms 7896 KB Output is correct
14 Correct 291 ms 8516 KB Output is correct
15 Correct 464 ms 10572 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1993 ms 12224 KB Output is correct
2 Correct 1844 ms 11220 KB Output is correct
3 Correct 2912 ms 16012 KB Output is correct
4 Correct 353 ms 9320 KB Output is correct
5 Correct 429 ms 11076 KB Output is correct
6 Correct 748 ms 11048 KB Output is correct
7 Correct 1593 ms 11232 KB Output is correct
8 Correct 1944 ms 18052 KB Output is correct
9 Correct 3182 ms 23592 KB Output is correct
10 Correct 4745 ms 29220 KB Output is correct
11 Correct 4629 ms 27220 KB Output is correct
12 Correct 5904 ms 21912 KB Output is correct
13 Correct 6726 ms 24008 KB Output is correct
14 Execution timed out 8064 ms 24624 KB Time limit exceeded
15 Execution timed out 8071 ms 29360 KB Time limit exceeded
16 Execution timed out 8045 ms 34824 KB Time limit exceeded
17 Execution timed out 8044 ms 33376 KB Time limit exceeded