제출 #511188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
511188		600Mihnea	Regions (IOI09_regions)	C++17	100 / 100	4141 ms	41808 KiB

regions

#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e5 + 7;
const int R = 25000 + 7;
const int CNT = 100;
int n;
int r;
int q;
int par[N];
int id[N];
int type[N];
vector<int> g[N];
vector<int> pos[R];
vector<int> verts[R];
int low[N];
int high[N];
int top;
int solution[CNT + 7][R];
int act[CNT + 7];
int who[CNT + 7];
int y;

void build(int a) {
  low[a] = ++top;
  verts[type[a]].push_back(a);
  pos[type[a]].push_back(top);
  for (auto &b : g[a]) {
    build(b);
  }
  high[a] = top;
}

int getcnt(int prefix, int value) {
  int sol = 0, low = 0, high = (int) pos[value].size() - 1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (pos[value][mid] <= prefix) {
      sol = mid + 1;
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return sol;
}

void dfs(int a) {
  int t = type[a];
  if (id[t]) {
    act[id[t]]++;
  }
  for (auto &b : g[a]) {
    dfs(b);
  }
  for (int j = 1; j <= y; j++) {
    solution[j][type[a]] += act[j];
  }
  if (id[t]) {
    act[id[t]]--;
  }
}

signed main() {
  ///freopen ("input", "r", stdin);

  cin >> n >> r >> q;
  cin >> type[1];
  for (int i = 2; i <= n; i++) {
    cin >> par[i] >> type[i];
    g[par[i]].push_back(i);
  }
  build(1);
  vector<pair<int, int>> ord;
  for (int i = 1; i <= n; i++) {
    ord.push_back({(int) verts[i].size(), i});
  }
  sort(ord.rbegin(), ord.rend());
  for (int j = 0; j < min(n, CNT); j++) {
    int i = ord[j].second;
    y++;
    id[i] = y;
    who[y] = i;
  }
  dfs(1);

  for (int iq = 1; iq <= q; iq++) {
    int a, b;
    cin >> a >> b;
    if (id[a]) {
      cout << solution[id[a]][b] << "\n";
      continue;
    }
    int sol = 0;
    for (auto &v : verts[a]) {
      sol += getcnt(high[v], b) - getcnt(low[v] - 1, b);
    }
    cout << sol << endl;
  }
  return 0;
}

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