제출 #415180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415180		Alex_tz307	Regions (IOI09_regions)	C++17	80 / 100	8071 ms	34824 KiB

regions

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5;
const int MAXR = 25 * 1e3;
int r[MAXN], timer, in[MAXN], out[MAXN];
vector<int> G[MAXN], R[MAXR], pos[MAXR];

void dfs(int u) {
  in[u] = ++timer;
  pos[r[u]].emplace_back(in[u]);
  for (int v : G[u])
    dfs(v);
  out[u] = timer;
}

int solve(int r1, int r2) {
  int ans = 0;
  for (int u : R[r1]) {
    int n = pos[r2].size(), st, dr, step, aux;
    for (step = 1; step < n; step <<= 1);
    aux = step;
    for (st = 0; step; step >>= 1) {
      int ind = st | step;
      if (ind <= n && pos[r2][ind - 1] < in[u])
        st |= step;
    }
    step = aux;
    for (dr = 0; step; step >>= 1) {
      int ind = dr | step;
      if (ind <= n && pos[r2][ind - 1] <= out[u])
        dr |= step;
    }
    ans += dr - st;
  }
  return ans;
}

int main() {
  int n, Q;
  cin >> n >> Q >> Q;
  for (int v = 0; v < n; ++v) {
    if (v == 0) {
      cin >> r[0];
      --r[0];
      R[r[0]].emplace_back(0);
      continue;
    }
    int u;
    cin >> u >> r[v];
    --r[v];
    G[u - 1].emplace_back(v);
    R[r[v]].emplace_back(v);
  }
  dfs(0);
  map<pair<int,int>,int> sol;
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    cin >> r1 >> r2;
    --r1, --r2;
    pair<int,int> p{r1, r2};
    auto it = sol.find(p);
    if (it != sol.end())
      cout << it->second << endl;
    else {
      int ans = solve(r1, r2);
      sol[p] = ans;
      cout << ans << endl;
    }
  }
  return 0;
}

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