Submission #1250330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250330		kunzaZa183	Regions (IOI09_regions)	C++20	100 / 100	3108 ms	109132 KiB

regions

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  int n, r, q;
  cin >> n >> r >> q;
  vector<int> region(n);
  vector<vector<int>> regions(r);
  cin >> region[0];
  region[0]--;
  regions[region[0]].push_back(0);
  vector<vector<int>> adj(n);
  for (int i = 1; i < n; i++) {
    int x;
    cin >> x;
    adj[x - 1].push_back(i);
    cin >> region[i];
    region[i]--;
    regions[region[i]].push_back(i);
  }

  vector<int> in(n), out(n);
  int ct = 0;
  function<void(int)> dfs = [&](int cur) {
    in[cur] = ct;
    for (auto a : adj[cur])
      dfs(a);
    out[cur] = ct++;
  };
  dfs(0);

  int k = sqrt(n / log2(n)) * 3;

  vector<vector<int>> coef(r);
  vector<vector<ll>> ans(r);

  for (int i = 0; i < r; i++) {
    if (regions[i].size() >= k) {
      coef[i].resize(n + 1);
      ans[i].resize(r);

      for (auto a : regions[i])
        coef[i][in[a]]++, coef[i][out[a]]--;

      for (int j = 1; j <= n; j++)
        coef[i][j] += coef[i][j - 1];

      for (int j = 0; j < n; j++)
        ans[i][region[j]] += coef[i][out[j]];
    }
  }

  vector<vector<int>> indexs(r);

  for (int i = 0; i < n; i++) {
    indexs[region[i]].push_back(out[i]);
  }

  for (auto &a : indexs)
    sort(begin(a), end(a));

  while (q--) {
    int a, b;
    cin >> a >> b;
    a--, b--;

    if (regions[a].size() >= k) {
      cout << ans[a][b] << endl;
    } else {
      int res = 0;
      for (auto x : regions[a])
        res += upper_bound(begin(indexs[b]), end(indexs[b]), out[x]) -
               lower_bound(begin(indexs[b]), end(indexs[b]), in[x]);
      cout << res << endl;
    }
  }
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85