oj.uz

Submission #415167

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

using namespace std;

const int MAXN = 2e5 + 1;
const int MAXR = 25 * 1e3 + 1;
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 = 1; v <= n; ++v) {
    if (v == 1) {
      cin >> r[1];
      R[r[1]].emplace_back(1);
      continue;
    }
    int u;
    cin >> u >> r[v];
    G[u].emplace_back(v);
    R[r[v]].emplace_back(v);
  }
  dfs(1);
  map<pair<int,int>,int> sol;
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    cin >> r1 >> r2;
    pair<int,int> p{r1, r2};
    auto it = sol.find(p);
    if (it != sol.end())
      cout << it->second << endl;
    else {
      int ans = solve(r1, r2);
      sol[p] = ans;
      cout << ans << endl;
    }
  }
  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 4 ms 6088 KB Output is correct
3 Correct 8 ms 6088 KB Output is correct
4 Correct 12 ms 6088 KB Output is correct
5 Correct 16 ms 6244 KB Output is correct
6 Correct 30 ms 6276 KB Output is correct
7 Correct 40 ms 6504 KB Output is correct
8 Correct 57 ms 6696 KB Output is correct
9 Correct 86 ms 6900 KB Output is correct
10 Correct 124 ms 7196 KB Output is correct
11 Correct 189 ms 7540 KB Output is correct
12 Correct 186 ms 8136 KB Output is correct
13 Correct 308 ms 7976 KB Output is correct
14 Correct 383 ms 8644 KB Output is correct
15 Correct 359 ms 10660 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1563 ms 12200 KB Output is correct
2 Correct 1946 ms 11288 KB Output is correct
3 Correct 2917 ms 16020 KB Output is correct
4 Correct 266 ms 9400 KB Output is correct
5 Correct 522 ms 11200 KB Output is correct
6 Correct 657 ms 11116 KB Output is correct
7 Correct 1164 ms 11244 KB Output is correct
8 Correct 1496 ms 18276 KB Output is correct
9 Correct 3436 ms 23552 KB Output is correct
10 Correct 6141 ms 29176 KB Output is correct
11 Correct 6919 ms 27308 KB Output is correct
12 Correct 6611 ms 21928 KB Output is correct
13 Correct 7146 ms 23980 KB Output is correct
14 Execution timed out 8073 ms 24312 KB Time limit exceeded
15 Execution timed out 8012 ms 28536 KB Time limit exceeded
16 Execution timed out 8023 ms 34768 KB Time limit exceeded
17 Correct 7981 ms 34232 KB Output is correct