oj.uz

Submission #415185

# Submission time Handle Problem Language Result Execution time Memory
415185 2021-05-31T16:17:49 Z Alex_tz307 Regions (IOI09_regions) C++17
90 / 100
 8000 ms 35672 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 << '\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 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 10 ms 6088 KB Output is correct
5 Correct 12 ms 6216 KB Output is correct
6 Correct 31 ms 6336 KB Output is correct
7 Correct 38 ms 6396 KB Output is correct
8 Correct 26 ms 6496 KB Output is correct
9 Correct 38 ms 6868 KB Output is correct
10 Correct 142 ms 7160 KB Output is correct
11 Correct 136 ms 7704 KB Output is correct
12 Correct 203 ms 8032 KB Output is correct
13 Correct 277 ms 7964 KB Output is correct
14 Correct 375 ms 8460 KB Output is correct
15 Correct 361 ms 10516 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1768 ms 12468 KB Output is correct
2 Correct 1980 ms 11352 KB Output is correct
3 Correct 2878 ms 16096 KB Output is correct
4 Correct 473 ms 9464 KB Output is correct
5 Correct 393 ms 11136 KB Output is correct
6 Correct 938 ms 11000 KB Output is correct
7 Correct 1262 ms 11396 KB Output is correct
8 Correct 1593 ms 18232 KB Output is correct
9 Correct 2785 ms 23652 KB Output is correct
10 Correct 4837 ms 29368 KB Output is correct
11 Correct 5153 ms 27280 KB Output is correct
12 Correct 5443 ms 22124 KB Output is correct
13 Correct 6557 ms 24024 KB Output is correct
14 Execution timed out 8015 ms 24900 KB Time limit exceeded
15 Execution timed out 8064 ms 29892 KB Time limit exceeded
16 Correct 7327 ms 35672 KB Output is correct
17 Correct 6739 ms 33980 KB Output is correct