제출 #511177

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

regions

#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e5 + 7;
const int M = 500;
int n;
int r;
int q;
int par[N];
int type[N];
vector<int> g[N];
vector<int> pos[N];
vector<int> verts[N];
int low[N];
int high[N];
int top;

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;
}

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);
  for (int iq = 1; iq <= q; iq++) {
    int a, b;
    cin >> a >> b;
    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: 65 / 85