제출 #1146600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146600		mannshah1211	Regions (IOI09_regions)	C++20	85 / 100	8093 ms	25656 KiB

regions

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "deb.h"
#else
#define debug(...) 
#endif

const int B = 450;

void solve() {
  int n, r, q;
  cin >> n >> r >> q;
  vector<int> p(n), region(n);
  cin >> region[0];
  --region[0];
  vector<vector<int>> employees(r), g(n);
  employees[region[0]].push_back(0);
  for (int i = 1; i < n; i++) {
    cin >> p[i] >> region[i];
    --p[i]; --region[i];
    employees[region[i]].push_back(i);
    g[p[i]].push_back(i);
    g[i].push_back(p[i]);
  }
  vector<int> ord(r);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    return (employees[i].size() < employees[j].size());
  });
  vector<int> tin(n), tout(n);
  int timer = 0;
  auto Dfs = [&](auto&& self, int v, int pr) -> void {
    tin[v] = timer++;
    for (int u : g[v]) {
      if (u != pr) {
        self(self, u, v);
      }
    }
    tout[v] = timer;
  };
  Dfs(Dfs, 0, -1);
  vector<vector<int>> at(r, {-1});
  for (int i = 0; i < n; i++) {
    at[region[i]].push_back(tin[i]);
  }
  for (int i = 0; i < r; i++) {
    sort(at[i].begin(), at[i].end());
    at[i].push_back(n);
  }
  auto in_subtree = [&](int k, int v) {
    int l = tin[v], r = tout[v];
    return lower_bound(at[k].begin(), at[k].end(), r) - lower_bound(at[k].begin(), at[k].end(), l);
  };
  while (q--) {
    int r1, r2;
    cin >> r1 >> r2;
    --r1; --r2;
    int ans = 0;
    for (int e : employees[r1]) {
      ans += in_subtree(r2, e);
    }
    cout << ans << '\n';
    fflush(stdout);
  } 
}

int main() {
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

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