Submission #754545

#	Time	Username	Problem	Language	Result	Execution time	Memory
754545		asdfgrace	Regions (IOI09_regions)	C++17	100 / 100	7656 ms	34580 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
typedef long long i64;
const int INF = 1000000007; //998244353;

template <class T> struct FenwickTree {
  vector<T> tree;
  int n;
  
  FenwickTree(int len) {
    n = len;
    tree = vector<T>(n, 0);
  }
  
  void upd(int k, T x) {
    for (; k < n; k |= k + 1) {
      tree[k] += x;
    }
  }
  
  T quer(int l, int r) {
    return sum(r) - sum(l - 1);
  }
  
  T sum(int k) {
    T res = 0;
    for (; k >= 0; k = (k & (k + 1)) - 1) {
      res += tree[k];
    }
    return res;
  }
};

struct S {
  int n, r, q, t;
  vector<int> par, reg, sub, ord, pos;
  vector<vector<int>> at, edg;
  map<pair<int, int>, pair<int, bool>> vis;

  void run() {
    cin >> n >> r >> q;
    par.resize(n); reg.resize(n); sub.resize(n, 1);
    ord.resize(n); pos.resize(n);
    at.resize(r); edg.resize(n);
    par[0] = 0; cin >> reg[0];
    --reg[0];
    at[reg[0]].push_back(0);
    for (int i = 1; i < n; ++i) {
      cin >> par[i] >> reg[i];
      --par[i]; --reg[i];
      at[reg[i]].push_back(i);
      edg[par[i]].push_back(i);
    }
    t = -1;
    dfs(0); PAR(sub); PAR(ord);
    for (int i = 0; i < r; ++i) {
      for (int j = 0; j < at[i].size(); ++j) {
        at[i][j] = ord[at[i][j]];
      }
      sort(at[i].begin(), at[i].end());
    }
    if (r <= 500) {
      solve1();
    } else {
      solve2();
    }
  }
  
  void dfs(int node) {
    ord[node] = ++t;
    pos[ord[node]] = node;
    for (auto next : edg[node]) {
      dfs(next);
      sub[ord[node]] += sub[ord[next]];
    }
  }
  
  void solve1() {
    vector<vector<int>> ans(r, vector<int>(r, 0));
    for (int i = 0; i < r; ++i) {
      PV(i);
      FenwickTree<int> cnt(n);
      PAR(at[i]);
      for (auto j : at[i]) {
        cnt.upd(j, 1);
      }
      for (int j = 0; j < n; ++j) {
        PV(j); PV(cnt.quer(j, j + sub[j] - 1));
        ans[reg[pos[j]]][i] += cnt.quer(j, j + sub[j] - 1);
      }
    }
    while (q--) {
      int a, b;
      cin >> a >> b;
      --a; --b;
      cout << ans[a][b] << endl;
    }
  }
  
  void solve2() {
    while (q--) {
      int a, b;
      cin >> a >> b;
      --a; --b;
      if (vis[{a, b}].second) {
        cout << vis[{a, b}].first << endl;
        continue;
      }
      int ans = 0;
      for (auto i : at[a]) {
        int l = lower_bound(at[b].begin(), at[b].end(), i)
          - at[b].begin();
        int r = lower_bound(at[b].begin(), at[b].end(), i + sub[i])
          - at[b].begin();
        PV(i); PV(l); PV(r);
        ans += max(r - l, 0);
      }
      vis[{a, b}] = {ans, true};
      cout << ans << endl;
    }
  }
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  auto sol = make_unique<S>();
  sol->run();
}

Compilation message (stderr)

regions.cpp: In member function 'void S::run()':
regions.cpp:64:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |       for (int j = 0; j < at[i].size(); ++j) {
      |                       ~~^~~~~~~~~~~~~~

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