Submission #1080834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080834		juicy	Regions (IOI09_regions)	C++17	13 / 100	95 ms	40612 KiB

regions

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5 + 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 (stderr)

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 / 15
• Subtask 2: 0 / 85