Submission #1248042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248042		lucaskojima	Regions (IOI09_regions)	C++17	100 / 100	2737 ms	28524 KiB

regions

#include "bits/stdc++.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0);

  int n, r, q; cin >> n >> r >> q;

  vector<vector<int>> adj(n + 1);
  vector<int> reg(n + 1);

  cin >> reg[1];
  for (int i = 2; i <= n; i++) {
    int p; cin >> p;
    adj[p].push_back(i);
    cin >> reg[i];
  }

  vector<vector<int>> comp(r + 1);
  vector<int> tin(n + 1), tout(n + 1), tin_node(n + 1);
  int t = 0;

  auto euler = [&](auto euler, int x) -> void {
    tin[x] = ++t;
    tin_node[tin[x]] = x;
    comp[reg[x]].push_back(tin[x]);
    for (int k : adj[x])
      euler(euler, k);
    tout[x] = t;
  };
  euler(euler, 1);

  const int SQ = sqrt(n);
  vector<vector<int>> calc;
  vector<int> reg_id(r + 1, -1);

  auto dfs = [&](auto dfs, int x, int k, int cnt) -> void {
    if (reg[x] == k) cnt++;
    calc[reg_id[k]][reg[x]] += cnt;
    for (int v : adj[x])
      dfs(dfs, v, k, cnt);
  };

  int cur = 0;
  for (int i = 1; i <= r; i++)
    if (sz(comp[i]) > SQ) {
      reg_id[i] = cur++;
      calc.push_back(vector<int>(r + 1));
      dfs(dfs, 1, i, 0);
    }

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

    if (sz(comp[a]) > SQ) {
      cout << calc[reg_id[a]][b] << endl;
    } else {
      int ans = 0;
      for (int x : comp[a]) {
        x = tin_node[x];
        ans += upper_bound(all(comp[b]), tout[x]) - lower_bound(all(comp[b]), tin[x]);
      }
      cout << ans << endl;
    }
  }
  return 0;
}

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