oj.uz

Submission #415158

# Submission time Handle Problem Language Result Execution time Memory
415158 2021-05-31T15:27:03 Z Alex_tz307 Regions (IOI09_regions) C++17
85 / 100
 8000 ms 31408 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 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);
  map<int,int> sol;
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    cin >> r1 >> r2;
    --r1, --r2;
    int h = r1 * MAXR + r2;
    auto it = sol.find(h);
    if (it != sol.end())
      cout << it->second << endl;
    else {
      int ans = solve(r1, r2);
      sol[h] = ans;
      cout << ans << endl;
    }
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6088 KB Output is correct
2 Correct 5 ms 6088 KB Output is correct
3 Correct 8 ms 6072 KB Output is correct
4 Correct 12 ms 6088 KB Output is correct
5 Correct 15 ms 6224 KB Output is correct
6 Correct 36 ms 6260 KB Output is correct
7 Correct 51 ms 6336 KB Output is correct
8 Correct 47 ms 6428 KB Output is correct
9 Correct 66 ms 6780 KB Output is correct
10 Correct 130 ms 6972 KB Output is correct
11 Correct 169 ms 7392 KB Output is correct
12 Correct 205 ms 7884 KB Output is correct
13 Correct 225 ms 7772 KB Output is correct
14 Correct 377 ms 8396 KB Output is correct
15 Correct 415 ms 10372 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1874 ms 11796 KB Output is correct
2 Correct 2253 ms 10876 KB Output is correct
3 Correct 3289 ms 15008 KB Output is correct
4 Correct 350 ms 8944 KB Output is correct
5 Correct 491 ms 10600 KB Output is correct
6 Correct 748 ms 10484 KB Output is correct
7 Correct 1108 ms 10936 KB Output is correct
8 Correct 1592 ms 17080 KB Output is correct
9 Correct 3517 ms 21380 KB Output is correct
10 Correct 5824 ms 26588 KB Output is correct
11 Correct 7679 ms 24248 KB Output is correct
12 Correct 6747 ms 20584 KB Output is correct
13 Correct 7672 ms 22036 KB Output is correct
14 Execution timed out 8066 ms 22124 KB Time limit exceeded
15 Execution timed out 8007 ms 26468 KB Time limit exceeded
16 Execution timed out 8016 ms 31408 KB Time limit exceeded
17 Correct 7678 ms 31296 KB Output is correct