Submission #265273

#	Time	Username	Problem	Language	Result	Execution time	Memory
265273		WLZ	Regions (IOI09_regions)	C++14	95 / 100	8031 ms	29284 KiB

regions

#include <bits/stdc++.h>
using namespace std;

int n, r, q, cur = 0;
vector<int> h, s;
vector< vector<int> > g;
vector< vector< pair<int, int> > > reg;

int dfs(int u) {
  int st = cur++;
  int en = st;
  for (auto& v : g[u]) {
    en = dfs(v);
  }
  reg[h[u]].push_back({st, 1});
  reg[h[u]].push_back({en, -1});
  return en;
}

long long solve(int r1, int r2) {
  int cur = 0, idx = -1;
  long long ans = 0;
  for (auto& p : reg[r2]) {
    if (p.second == -1) {
      continue;
    }
    while (idx + 1 < (int) reg[r1].size() && reg[r1][idx + 1].first < p.first) {
      idx++;
      cur += reg[r1][idx].second;
    }
    ans += (long long) cur;
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> r >> q;
  h.resize(n + 1);
  s.resize(n + 1);
  cin >> h[1];
  g.resize(n + 1);
  for (int i = 2; i <= n; i++) {
    cin >> s[i] >> h[i];
    g[s[i]].push_back(i);
  }
  reg.resize(r + 1);
  dfs(1);
  for (int i = 1; i <= r; i++) {
    sort(reg[i].begin(), reg[i].end());
  }
  while (q--) {
    int r1, r2;
    cin >> r1 >> r2;
    cout << solve(r1, r2) << endl;
  }
  return 0;
}

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