oj.uz

Submission #415154

# Submission time Handle Problem Language Result Execution time Memory
415154 2021-05-31T15:24:09 Z Alex_tz307 Regions (IOI09_regions) C++17
85 / 100
 8000 ms 66184 KB 
#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

const int MAXN = 2e5;
const int MAXR = 25 * 1e3;
const int mod = 1572869;
int r[MAXN], timer, in[MAXN], out[MAXN];
vector<int> G[MAXN], R[MAXR], pos[MAXR];
vector<pair<int,int>> H[mod];

void dfs(int u) {
  in[u] = ++timer;
  pos[r[u]].emplace_back(in[u]);
  for (int v : G[u])
    dfs(v);
  out[u] = timer;
}

void Insert(int x, int val) {
  H[x % mod].emplace_back(x, val);
}

int Find(int x) {
  int key = x % mod;
  for (auto it : H[key])
    if (it.first == x)
      return it.second;
  return -1;
}

int solve(int r1, int r2) {
  int ans = 0;
  for (int u : R[r1]) {
    int st = lower_bound(pos[r2].begin(), pos[r2].end(), in[u]) - pos[r2].begin();
    int dr = upper_bound(pos[r2].begin(), pos[r2].end(), out[u]) - pos[r2].begin();
    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);
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    cin >> r1 >> r2;
    --r1, --r2;
    int h = r1 * MAXR + r2;
    int ans = Find(h);
    if (ans != -1)
      cout << ans << endl;
    else {
      int ans = solve(r1, r2);
      Insert(h, ans);
      cout << ans << endl;
    }
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 43136 KB Output is correct
2 Correct 28 ms 43072 KB Output is correct
3 Correct 29 ms 43120 KB Output is correct
4 Correct 32 ms 43108 KB Output is correct
5 Correct 40 ms 43148 KB Output is correct
6 Correct 63 ms 43184 KB Output is correct
7 Correct 53 ms 43220 KB Output is correct
8 Correct 78 ms 43200 KB Output is correct
9 Correct 119 ms 43700 KB Output is correct
10 Correct 94 ms 43836 KB Output is correct
11 Correct 232 ms 44180 KB Output is correct
12 Correct 201 ms 44752 KB Output is correct
13 Correct 300 ms 44660 KB Output is correct
14 Correct 324 ms 45048 KB Output is correct
15 Correct 416 ms 47012 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1768 ms 48276 KB Output is correct
2 Correct 1675 ms 47496 KB Output is correct
3 Correct 2793 ms 50940 KB Output is correct
4 Correct 421 ms 45596 KB Output is correct
5 Correct 605 ms 46948 KB Output is correct
6 Correct 887 ms 46964 KB Output is correct
7 Correct 1076 ms 47640 KB Output is correct
8 Correct 1754 ms 52916 KB Output is correct
9 Correct 2641 ms 56224 KB Output is correct
10 Correct 5432 ms 60824 KB Output is correct
11 Correct 5365 ms 57804 KB Output is correct
12 Correct 5688 ms 56308 KB Output is correct
13 Correct 7108 ms 57108 KB Output is correct
14 Execution timed out 8063 ms 57116 KB Time limit exceeded
15 Execution timed out 8076 ms 61316 KB Time limit exceeded
16 Execution timed out 8026 ms 66184 KB Time limit exceeded
17 Correct 6800 ms 65176 KB Output is correct