oj.uz

Submission #415163

# Submission time Handle Problem Language Result Execution time Memory
415163 2021-05-31T15:29:46 Z Alex_tz307 Regions (IOI09_regions) C++17
85 / 100
 8000 ms 35428 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 5 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 11 ms 6200 KB Output is correct
5 Correct 16 ms 6216 KB Output is correct
6 Correct 33 ms 6336 KB Output is correct
7 Correct 53 ms 6312 KB Output is correct
8 Correct 43 ms 6460 KB Output is correct
9 Correct 67 ms 7020 KB Output is correct
10 Correct 137 ms 7364 KB Output is correct
11 Correct 210 ms 7436 KB Output is correct
12 Correct 227 ms 8112 KB Output is correct
13 Correct 249 ms 8024 KB Output is correct
14 Correct 356 ms 8496 KB Output is correct
15 Correct 404 ms 10620 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1727 ms 12228 KB Output is correct
2 Correct 1937 ms 11268 KB Output is correct
3 Correct 2819 ms 16100 KB Output is correct
4 Correct 389 ms 9480 KB Output is correct
5 Correct 548 ms 11180 KB Output is correct
6 Correct 685 ms 11100 KB Output is correct
7 Correct 925 ms 11320 KB Output is correct
8 Correct 1677 ms 18156 KB Output is correct
9 Correct 3392 ms 23548 KB Output is correct
10 Correct 5179 ms 29288 KB Output is correct
11 Correct 5633 ms 27240 KB Output is correct
12 Correct 5748 ms 21892 KB Output is correct
13 Correct 6312 ms 24172 KB Output is correct
14 Execution timed out 8007 ms 25032 KB Time limit exceeded
15 Execution timed out 8032 ms 29636 KB Time limit exceeded
16 Execution timed out 8009 ms 35428 KB Time limit exceeded
17 Correct 7374 ms 34212 KB Output is correct