oj.uz

Submission #415220

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

using namespace std;

const int MAXN = 2e5;
const int MAXR = 25 * 1e3;
const int BLOCK = 445;
int m, r[MAXN], timer, in[MAXN], out[MAXN], cnt_large, ind[MAXR], dp[MAXR], child[BLOCK][MAXR];
vector<int> G[MAXN], R[MAXR], pos[MAXR];

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, int region) {
  if (r[u] == region)
    for (int i = 0; i < m; ++i)
      child[ind[region]][i] += dp[i];
  ++dp[r[u]];
  for (int v : G[u])
    dfs2(v, region);
  --dp[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){
      ind[i] = cnt_large++;
      for (int j = 0; j < m; ++j)
        dp[j] = 0;
      dfs2(0, i);
    }
  map<pair<int,int>,int> sol;
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    cin >> r1 >> r2;
    --r1, --r2;
    if ((int)R[r2].size() > BLOCK) {
      cout << child[ind[r2]][r1] << '\n';
      cout.flush();
      continue;
    }
    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 5 ms 6088 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 5 ms 6196 KB Output is correct
4 Correct 8 ms 6088 KB Output is correct
5 Correct 12 ms 6216 KB Output is correct
6 Correct 42 ms 6448 KB Output is correct
7 Correct 53 ms 6412 KB Output is correct
8 Correct 44 ms 6456 KB Output is correct
9 Correct 40 ms 6868 KB Output is correct
10 Correct 105 ms 7084 KB Output is correct
11 Correct 155 ms 7448 KB Output is correct
12 Correct 232 ms 8132 KB Output is correct
13 Correct 263 ms 7964 KB Output is correct
14 Correct 362 ms 8704 KB Output is correct
15 Correct 390 ms 10604 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1677 ms 12804 KB Output is correct
2 Correct 1806 ms 11428 KB Output is correct
3 Correct 3314 ms 17248 KB Output is correct
4 Correct 388 ms 9496 KB Output is correct
5 Correct 425 ms 11284 KB Output is correct
6 Correct 972 ms 13080 KB Output is correct
7 Correct 1411 ms 12216 KB Output is correct
8 Correct 1987 ms 23416 KB Output is correct
9 Correct 3419 ms 23688 KB Output is correct
10 Correct 5305 ms 36140 KB Output is correct
11 Correct 6575 ms 27288 KB Output is correct
12 Correct 7031 ms 20896 KB Output is correct
13 Correct 6863 ms 23160 KB Output is correct
14 Execution timed out 8032 ms 23296 KB Time limit exceeded
15 Execution timed out 8079 ms 29120 KB Time limit exceeded
16 Execution timed out 8015 ms 37376 KB Time limit exceeded
17 Execution timed out 8006 ms 37804 KB Time limit exceeded