Submission #415187

#	Time	Username	Problem	Language	Result	Execution time	Memory
415187		Alex_tz307	Regions (IOI09_regions)	C++17	85 / 100	8087 ms	35524 KiB

regions

#include <bits/stdc++.h>

using namespace std;

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

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

int solve(int r1, int r2) {
  int ans = 0;
  for (int u : R[r1]) {
    int n = pos[r2].size();
    int st = n, dr = n, l = 0, r = n - 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (in[u] <= pos[r2][mid]) {
        st = mid;
        r = mid - 1;
      } else l = mid + 1;
    }
    l = 0, r = n - 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (out[u] < pos[r2][mid]) {
        dr = mid;
        r = mid - 1;
      } else l = mid + 1;
    }
    ans += dr - st;
  }
  return ans;
}

int main() {
  int n, Q;
  scanf("%d %d %d", &n, &Q, &Q);
  for (int v = 0; v < n; ++v) {
    if (v == 0) {
      scanf("%d", &r[0]);
      --r[0];
      R[r[0]].emplace_back(0);
      continue;
    }
    int u;
    scanf("%d %d", &u, &r[v]);
    --r[v];
    G[u - 1].emplace_back(v);
    R[r[v]].emplace_back(v);
  }
  dfs(0);
  map<pair<int,int>,int> sol;
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    scanf("%d %d", &r1, &r2);
    --r1, --r2;
    pair<int,int> p{r1, r2};
    auto it = sol.find(p);
    if (it != sol.end()) {
      printf("%d\n", it->second);
      fflush(stdout);
    }
    else {
      int ans = solve(r1, r2);
      sol[p] = ans;
      printf("%d\n", ans);
      fflush(stdout);
    }
  }
  return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d %d %d", &n, &Q, &Q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:48:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |       scanf("%d", &r[0]);
      |       ~~~~~^~~~~~~~~~~~~
regions.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d %d", &u, &r[v]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d %d", &r1, &r2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

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