oj.uz

Submission #753756

# Submission time Handle Problem Language Result Execution time Memory
753756 2023-06-05T23:02:17 Z taher Regions (IOI09_regions) C++17
100 / 100
 3224 ms 44008 KB 
 #include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "C:\GCC\debug.h"
#else
#define debug(...) void(42)
#endif

const int R = 25005;
map<int, int> done[R];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, r, q;
  cin >> n >> r >> q;

  vector<vector<int>> at(r);
  vector<vector<int>> adj(n);

  int hRegion;
  cin >> hRegion;
  hRegion--;
  at[hRegion].push_back(0);

  for (int i = 1; i < n; i++) {
    int par, hCurrent;
    cin >> par >> hCurrent;
    --par;
    --hCurrent;
    at[hCurrent].push_back(i);
    adj[par].push_back(i);
  }

  vector<int> euler_tour;
  vector<int> in(n);
  vector<int> out(n);
  function<void(int)> Dfs = [&](int u) {
    in[u] = (int) euler_tour.size();
    euler_tour.push_back(u);

    for (auto v : adj[u]) {
      Dfs(v);
    }

    out[u] = (int) euler_tour.size() - 1;
  };

  Dfs(0);

  vector<vector<int>> all(r);
  vector<vector<array<int, 2>>> inters(r);
  for (int y = 0; y < r; y++) {
    for (auto pt : at[y]) {
      all[y].push_back(in[pt]);
      inters[y].push_back({in[pt], +1});
      inters[y].push_back({out[pt], -1});
    }
    sort(all[y].begin(), all[y].end());
    sort(inters[y].begin(), inters[y].end());
  }

  auto Get = [&](int x, int y) {

    int ptr = 0;
    int cnt = 0;
    int res = 0;
    for (int i = 0; i < (int) all[y].size(); i++) {
      while (ptr < (int) inters[x].size() && inters[x][ptr][0] < all[y][i]) {
        cnt += inters[x][ptr][1];
        ++ptr;
      }
      res += cnt;
    }

    return res;
  };

  for (int i = 0; i < q; i++) {
    array<int, 2> b;
    cin >> b[0] >> b[1];
    --b[0], --b[1];

    if (done[b[0]].count(b[1])) {
      cout << done[b[0]][b[1]] << '\n';
    } else {
      int res = Get(b[0], b[1]);
      done[b[0]][b[1]] = res;
      cout << res << '\n';
    }

    cout.flush();
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1488 KB Output is correct
2 Correct 1 ms 1488 KB Output is correct
3 Correct 2 ms 1500 KB Output is correct
4 Correct 6 ms 1516 KB Output is correct
5 Correct 6 ms 1488 KB Output is correct
6 Correct 22 ms 1680 KB Output is correct
7 Correct 35 ms 1724 KB Output is correct
8 Correct 38 ms 1768 KB Output is correct
9 Correct 47 ms 2504 KB Output is correct
10 Correct 64 ms 2816 KB Output is correct
11 Correct 108 ms 3344 KB Output is correct
12 Correct 104 ms 4308 KB Output is correct
13 Correct 170 ms 4276 KB Output is correct
14 Correct 133 ms 5184 KB Output is correct
15 Correct 130 ms 8860 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 11032 KB Output is correct
2 Correct 800 ms 9704 KB Output is correct
3 Correct 1108 ms 15348 KB Output is correct
4 Correct 211 ms 6104 KB Output is correct
5 Correct 236 ms 8804 KB Output is correct
6 Correct 475 ms 8868 KB Output is correct
7 Correct 720 ms 10372 KB Output is correct
8 Correct 910 ms 19600 KB Output is correct
9 Correct 1264 ms 25988 KB Output is correct
10 Correct 1855 ms 34216 KB Output is correct
11 Correct 2443 ms 30588 KB Output is correct
12 Correct 1406 ms 25604 KB Output is correct
13 Correct 1713 ms 27388 KB Output is correct
14 Correct 2053 ms 29128 KB Output is correct
15 Correct 2730 ms 36960 KB Output is correct
16 Correct 3224 ms 44008 KB Output is correct
17 Correct 2360 ms 42148 KB Output is correct