oj.uz

Submission #1080835

# Submission time Handle Problem Language Result Execution time Memory
1080835 2024-08-29T14:44:17 Z juicy Regions (IOI09_regions) C++17
13 / 100
 113 ms 64848 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5, R = 25005, S = 450;

int n, r, q;
int h[N], tin[N], tout[N], down[S][R], up[S][R], pr[N], ind[N], f[N];
vector<int> g[N], pos[R];
vector<array<int, 2>> events[R];

int order;

void dfs(int u) {
  tin[u] = ++order;
  for (int v : g[u]) {
    dfs(v);
  }
  tout[u] = order;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> r >> q;
  for (int i = 1; i <= n; ++i) {
    if (i > 1) {
      cin >> pr[i] >> h[i];
      g[pr[i]].push_back(i);
    } else {
      cin >> h[i];
    }
    pos[h[i]].push_back(i);
  }
  dfs(1);
  int k = 0;
  for (int i = 1; i <= n; ++i) {
    if (pos[i].size() >= S) {
      ind[i] = ++k;
      fill(f + 1, f + n + 1, 0);
      for (auto x : pos[i]) {
        ++f[x];
      }
      for (int j = 1; j <= n; ++j) {
        f[j] += f[pr[j]];
        down[k][h[j]] += f[j];
      }
      fill(f + 1, f + n + 1, 0);
      for (auto x : pos[i]) {
        ++f[x];
      }
      for (int j = n; j >= 1; --j) {
        for (int x : g[j]) {
          f[j] += f[x];
        }
        up[k][h[j]] += f[j];
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (auto &x : pos[i]) {
      events[i].push_back({tin[x] - 1, -1});
      events[i].push_back({tout[x], 1});
      x = tin[x];
    }
    sort(pos[i].begin(), pos[i].end());
    sort(events[i].begin(), events[i].end());
  }
  while (q--) {
    int x, y; cin >> x >> y;
    if (ind[x]) {
      cout << down[ind[x]][y] << endl;
      continue;
    }
    if (ind[y]) {
      cout << up[ind[y]][x] << endl;
      continue;
    }
    int j = 0, res = 0;
    for (auto [t, d] : events[x]) {
      while (j < pos[y].size() && pos[y][j] <= t) {
        ++j;
      }
      res += d * j;
    }
    cout << res << endl;
  }
  return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:87:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |       while (j < pos[y].size() && pos[y][j] <= t) {
      |              ~~^~~~~~~~~~~~~~~

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10836 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 3 ms 10840 KB Output is correct
4 Correct 4 ms 10840 KB Output is correct
5 Correct 5 ms 10840 KB Output is correct
6 Correct 10 ms 10840 KB Output is correct
7 Correct 15 ms 10840 KB Output is correct
8 Correct 16 ms 10840 KB Output is correct
9 Correct 25 ms 11352 KB Output is correct
10 Correct 49 ms 11352 KB Output is correct
11 Correct 60 ms 11864 KB Output is correct
12 Correct 74 ms 12376 KB Output is correct
13 Correct 92 ms 12120 KB Output is correct
14 Runtime error 22 ms 24144 KB Execution killed with signal 11
15 Runtime error 18 ms 27588 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 33360 KB Execution killed with signal 11
2 Runtime error 32 ms 31296 KB Execution killed with signal 11
3 Runtime error 36 ms 35928 KB Execution killed with signal 11
4 Runtime error 20 ms 24288 KB Execution killed with signal 11
5 Runtime error 17 ms 26456 KB Execution killed with signal 11
6 Runtime error 43 ms 33616 KB Execution killed with signal 11
7 Runtime error 31 ms 30032 KB Execution killed with signal 11
8 Runtime error 80 ms 52304 KB Execution killed with signal 11
9 Runtime error 44 ms 36688 KB Execution killed with signal 11
10 Runtime error 108 ms 64848 KB Execution killed with signal 11
11 Runtime error 71 ms 36396 KB Execution killed with signal 11
12 Runtime error 57 ms 40532 KB Execution killed with signal 11
13 Runtime error 76 ms 40016 KB Execution killed with signal 11
14 Runtime error 113 ms 48804 KB Execution killed with signal 11
15 Runtime error 68 ms 49744 KB Execution killed with signal 11
16 Runtime error 68 ms 52052 KB Execution killed with signal 11
17 Runtime error 84 ms 59724 KB Execution killed with signal 11