oj.uz

Submission #415249

# Submission time Handle Problem Language Result Execution time Memory
415249 2021-05-31T18:09:42 Z Alex_tz307 Regions (IOI09_regions) C++17
35 / 100
 4818 ms 47712 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5;
const int MAXR = 25 * 1e3;
const int BLOCK = 450;
int m, r[MAXN], timer, in[MAXN], out[MAXN], cnt_large, ind[MAXR], root[BLOCK][MAXR];
vector<int> G[MAXN], R[MAXR], pos[MAXR];
bitset<MAXN> is_large;
map<int,int> large;

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) {
  for (auto it : large)
    root[it.first][r[u]] += it.second;
  if (is_large[r[u]])
    ++large[r[u]];
  for (int v : G[u])
    dfs2(v);
  if (is_large[r[u]])
    --large[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) {
      is_large[i] = true;
      ind[i] = cnt_large++;
    }
  dfs2(0);
  map<pair<int,int>,int> sol;
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    cin >> r1 >> r2;
    --r1, --r2;
    if ((int)R[r1].size() > BLOCK)
      cout << root[ind[r1]][r2] << '\n';
    else {
      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 5 ms 6088 KB Output is correct
3 Correct 7 ms 6088 KB Output is correct
4 Correct 11 ms 6216 KB Output is correct
5 Correct 13 ms 6216 KB Output is correct
6 Correct 37 ms 6336 KB Output is correct
7 Correct 34 ms 6416 KB Output is correct
8 Correct 47 ms 6444 KB Output is correct
9 Correct 68 ms 7204 KB Output is correct
10 Correct 130 ms 7268 KB Output is correct
11 Correct 172 ms 7488 KB Output is correct
12 Correct 171 ms 8384 KB Output is correct
13 Correct 271 ms 8036 KB Output is correct
14 Correct 376 ms 8484 KB Output is correct
15 Correct 376 ms 13136 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1626 ms 13136 KB Output isn't correct
2 Incorrect 1491 ms 11476 KB Output isn't correct
3 Incorrect 2552 ms 18448 KB Output isn't correct
4 Correct 254 ms 9444 KB Output is correct
5 Correct 542 ms 12712 KB Output is correct
6 Runtime error 61 ms 18072 KB Execution killed with signal 11
7 Runtime error 85 ms 20228 KB Execution killed with signal 11
8 Runtime error 120 ms 28420 KB Execution killed with signal 11
9 Correct 3328 ms 24796 KB Output is correct
10 Runtime error 173 ms 38872 KB Execution killed with signal 11
11 Correct 4818 ms 27412 KB Output is correct
12 Runtime error 200 ms 33840 KB Execution killed with signal 11
13 Runtime error 219 ms 33752 KB Execution killed with signal 11
14 Runtime error 221 ms 33860 KB Execution killed with signal 11
15 Runtime error 197 ms 40748 KB Execution killed with signal 11
16 Runtime error 214 ms 47712 KB Execution killed with signal 11
17 Runtime error 201 ms 46104 KB Execution killed with signal 11