oj.uz

Submission #415246

# Submission time Handle Problem Language Result Execution time Memory
415246 2021-05-31T18:00:27 Z Alex_tz307 Regions (IOI09_regions) C++17
75 / 100
 8000 ms 33732 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], dp[MAXR], root[BLOCK][MAXR], child[BLOCK][MAXR];
vector<int> G[MAXN], R[MAXR], pos[MAXR], S;
bitset<MAXN> is_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 (int region : S)
    ++root[ind[region]][r[u]];
  if (is_large[r[u]]) {
    for (int i = 0; i < m; ++i)
      child[ind[r[u]]][i] += dp[i];
    S.emplace_back(r[u]);
  }
  ++dp[r[u]];
  for (int v : G[u])
    dfs2(v);
  if (is_large[r[u]])
    S.pop_back();
  --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) {
      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 if ((int)R[r2].size() > BLOCK)
      cout << child[ind[r2]][r1] << '\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 6 ms 6088 KB Output is correct
2 Correct 5 ms 6088 KB Output is correct
3 Correct 9 ms 6088 KB Output is correct
4 Correct 10 ms 6216 KB Output is correct
5 Correct 17 ms 6216 KB Output is correct
6 Correct 29 ms 6304 KB Output is correct
7 Correct 49 ms 6436 KB Output is correct
8 Correct 38 ms 6460 KB Output is correct
9 Correct 88 ms 7036 KB Output is correct
10 Correct 145 ms 7136 KB Output is correct
11 Correct 199 ms 7492 KB Output is correct
12 Correct 192 ms 8412 KB Output is correct
13 Correct 299 ms 7892 KB Output is correct
14 Correct 302 ms 8728 KB Output is correct
15 Correct 363 ms 12036 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3082 ms 12796 KB Output is correct
2 Correct 2044 ms 11240 KB Output is correct
3 Correct 7627 ms 17268 KB Output is correct
4 Correct 488 ms 9580 KB Output is correct
5 Correct 451 ms 11992 KB Output is correct
6 Correct 1474 ms 14724 KB Output is correct
7 Correct 1212 ms 12568 KB Output is correct
8 Execution timed out 8070 ms 24620 KB Time limit exceeded
9 Correct 3333 ms 24308 KB Output is correct
10 Execution timed out 8036 ms 33732 KB Time limit exceeded
11 Correct 6650 ms 27580 KB Output is correct
12 Correct 2712 ms 19712 KB Output is correct
13 Correct 5059 ms 21816 KB Output is correct
14 Correct 5503 ms 24964 KB Output is correct
15 Execution timed out 8082 ms 22828 KB Time limit exceeded
16 Execution timed out 8042 ms 25880 KB Time limit exceeded
17 Execution timed out 8066 ms 27060 KB Time limit exceeded