Submission #271935

#	Time	Username	Problem	Language	Result	Execution time	Memory
271935		WLZ	Regions (IOI09_regions)	C++14	75 / 100	8106 ms	112488 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);
  int k = floor(sqrt(n));
  for (int i = 1; i <= r; i++) {
    sort(reg[i].begin(), reg[i].end());
  }
  vector< vector<long long> > ans1(r + 1), ans2(r + 1);
  for (int i = 1; i <= r; i++) {
    if ((int) reg[i].size() >= k) {
      ans1[i].resize(r + 1);
      ans2[i].resize(r + 1);
      for (int j = 1; j <= r; j++) {
        if (i == j) {
          continue;
        }
        ans1[i][j] = solve(i, j);
        ans2[i][j] = solve(j, i);
      }
    }
  }
  while (q--) {
    int r1, r2;
    cin >> r1 >> r2;
    if ((int) reg[r1].size() >= k) {
      cout << ans1[r1][r2] << endl;
    } else if ((int) reg[r2].size() >= k) {
      cout << ans2[r2][r1] << endl;
    } else {
      cout << solve(r1, r2) << endl;
    }
  }
  return 0;
}

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