oj.uz

Submission #415203

# Submission time Handle Problem Language Result Execution time Memory
415203 2021-05-31T16:39:23 Z Alex_tz307 Regions (IOI09_regions) C++17
85 / 100
 8000 ms 35624 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() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  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 << '\n';
      cout.flush();
    }
    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 4 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 8 ms 6216 KB Output is correct
5 Correct 15 ms 6216 KB Output is correct
6 Correct 24 ms 6272 KB Output is correct
7 Correct 31 ms 6344 KB Output is correct
8 Correct 37 ms 6520 KB Output is correct
9 Correct 51 ms 6976 KB Output is correct
10 Correct 90 ms 7104 KB Output is correct
11 Correct 141 ms 7488 KB Output is correct
12 Correct 173 ms 8180 KB Output is correct
13 Correct 152 ms 7884 KB Output is correct
14 Correct 393 ms 8500 KB Output is correct
15 Correct 324 ms 10720 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1695 ms 12224 KB Output is correct
2 Correct 1765 ms 11352 KB Output is correct
3 Correct 3062 ms 16156 KB Output is correct
4 Correct 393 ms 9432 KB Output is correct
5 Correct 525 ms 11160 KB Output is correct
6 Correct 463 ms 10948 KB Output is correct
7 Correct 1083 ms 11208 KB Output is correct
8 Correct 1442 ms 18252 KB Output is correct
9 Correct 2835 ms 23564 KB Output is correct
10 Correct 5324 ms 29144 KB Output is correct
11 Correct 5536 ms 27356 KB Output is correct
12 Correct 6029 ms 21920 KB Output is correct
13 Correct 7253 ms 23816 KB Output is correct
14 Execution timed out 8045 ms 23844 KB Time limit exceeded
15 Execution timed out 8083 ms 29448 KB Time limit exceeded
16 Correct 7716 ms 35624 KB Output is correct
17 Execution timed out 8000 ms 34224 KB Time limit exceeded