oj.uz

Submission #415183

# Submission time Handle Problem Language Result Execution time Memory
415183 2021-05-31T16:12:31 Z Alex_tz307 Regions (IOI09_regions) C++17
90 / 100
 8000 ms 35552 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();
    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 >> 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 4 ms 6088 KB Output is correct
2 Correct 6 ms 6088 KB Output is correct
3 Correct 9 ms 6184 KB Output is correct
4 Correct 7 ms 6184 KB Output is correct
5 Correct 17 ms 6224 KB Output is correct
6 Correct 33 ms 6272 KB Output is correct
7 Correct 55 ms 6408 KB Output is correct
8 Correct 51 ms 6440 KB Output is correct
9 Correct 58 ms 6888 KB Output is correct
10 Correct 84 ms 7156 KB Output is correct
11 Correct 139 ms 7624 KB Output is correct
12 Correct 201 ms 8064 KB Output is correct
13 Correct 264 ms 7952 KB Output is correct
14 Correct 405 ms 8492 KB Output is correct
15 Correct 451 ms 10536 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2012 ms 12416 KB Output is correct
2 Correct 2009 ms 11288 KB Output is correct
3 Correct 2947 ms 16072 KB Output is correct
4 Correct 392 ms 9404 KB Output is correct
5 Correct 477 ms 11156 KB Output is correct
6 Correct 609 ms 11220 KB Output is correct
7 Correct 1104 ms 11420 KB Output is correct
8 Correct 1507 ms 18328 KB Output is correct
9 Correct 3177 ms 23664 KB Output is correct
10 Correct 5547 ms 29248 KB Output is correct
11 Correct 5947 ms 27252 KB Output is correct
12 Correct 6146 ms 21884 KB Output is correct
13 Correct 6776 ms 23920 KB Output is correct
14 Execution timed out 8010 ms 24316 KB Time limit exceeded
15 Execution timed out 8038 ms 28768 KB Time limit exceeded
16 Correct 7888 ms 35552 KB Output is correct
17 Correct 7441 ms 33936 KB Output is correct