Submission #415154

#	Time	Username	Problem	Language	Result	Execution time	Memory
415154		Alex_tz307	Regions (IOI09_regions)	C++17	85 / 100	8076 ms	66184 KiB

regions

#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

const int MAXN = 2e5;
const int MAXR = 25 * 1e3;
const int mod = 1572869;
int r[MAXN], timer, in[MAXN], out[MAXN];
vector<int> G[MAXN], R[MAXR], pos[MAXR];
vector<pair<int,int>> H[mod];

void dfs(int u) {
  in[u] = ++timer;
  pos[r[u]].emplace_back(in[u]);
  for (int v : G[u])
    dfs(v);
  out[u] = timer;
}

void Insert(int x, int val) {
  H[x % mod].emplace_back(x, val);
}

int Find(int x) {
  int key = x % mod;
  for (auto it : H[key])
    if (it.first == x)
      return it.second;
  return -1;
}

int solve(int r1, int r2) {
  int ans = 0;
  for (int u : R[r1]) {
    int st = lower_bound(pos[r2].begin(), pos[r2].end(), in[u]) - pos[r2].begin();
    int dr = upper_bound(pos[r2].begin(), pos[r2].end(), out[u]) - pos[r2].begin();
    ans += dr - st;
  }
  return ans;
}

int main() {
  int n, Q;
  cin >> n >> Q >> Q;
  for (int v = 0; v < n; ++v) {
    if (v == 0) {
      cin >> r[0];
      --r[0];
      R[r[0]].emplace_back(0);
      continue;
    }
    int u;
    cin >> u >> r[v];
    --r[v];
    G[u - 1].emplace_back(v);
    R[r[v]].emplace_back(v);
  }
  dfs(0);
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    cin >> r1 >> r2;
    --r1, --r2;
    int h = r1 * MAXR + r2;
    int ans = Find(h);
    if (ans != -1)
      cout << ans << endl;
    else {
      int ans = solve(r1, r2);
      Insert(h, ans);
      cout << ans << endl;
    }
  }
  return 0;
}

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