oj.uz

Submission #415143

# Submission time Handle Problem Language Result Execution time Memory
415143 2021-05-31T15:12:09 Z Alex_tz307 Regions (IOI09_regions) C++17
90 / 100
 8000 ms 35584 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<pair<int,int>,int> sol;
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    cin >> r1 >> r2;
    --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 4 ms 6088 KB Output is correct
2 Correct 5 ms 6088 KB Output is correct
3 Correct 6 ms 6184 KB Output is correct
4 Correct 11 ms 6188 KB Output is correct
5 Correct 13 ms 6212 KB Output is correct
6 Correct 40 ms 6340 KB Output is correct
7 Correct 42 ms 6320 KB Output is correct
8 Correct 44 ms 6440 KB Output is correct
9 Correct 86 ms 6792 KB Output is correct
10 Correct 148 ms 7084 KB Output is correct
11 Correct 149 ms 7488 KB Output is correct
12 Correct 238 ms 8316 KB Output is correct
13 Correct 220 ms 7872 KB Output is correct
14 Correct 339 ms 8480 KB Output is correct
15 Correct 343 ms 10624 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1437 ms 12308 KB Output is correct
2 Correct 2195 ms 11472 KB Output is correct
3 Correct 2754 ms 16128 KB Output is correct
4 Correct 344 ms 9424 KB Output is correct
5 Correct 562 ms 11136 KB Output is correct
6 Correct 648 ms 11188 KB Output is correct
7 Correct 994 ms 11236 KB Output is correct
8 Correct 1382 ms 18124 KB Output is correct
9 Correct 2982 ms 23568 KB Output is correct
10 Correct 5433 ms 29180 KB Output is correct
11 Correct 5685 ms 27228 KB Output is correct
12 Correct 5904 ms 22004 KB Output is correct
13 Correct 6251 ms 23936 KB Output is correct
14 Execution timed out 8020 ms 24968 KB Time limit exceeded
15 Execution timed out 8025 ms 29844 KB Time limit exceeded
16 Correct 7805 ms 35584 KB Output is correct
17 Correct 7438 ms 34128 KB Output is correct