oj.uz

Submission #754545

# Submission time Handle Problem Language Result Execution time Memory
754545 2023-06-08T03:18:14 Z asdfgrace Regions (IOI09_regions) C++17
100 / 100
 7656 ms 34580 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
5 Correct 4 ms 336 KB Output is correct
6 Correct 20 ms 660 KB Output is correct
7 Correct 32 ms 464 KB Output is correct
8 Correct 46 ms 656 KB Output is correct
9 Correct 63 ms 1248 KB Output is correct
10 Correct 179 ms 1840 KB Output is correct
11 Correct 182 ms 1864 KB Output is correct
12 Correct 313 ms 3076 KB Output is correct
13 Correct 392 ms 2468 KB Output is correct
14 Correct 328 ms 3016 KB Output is correct
15 Correct 347 ms 5072 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 7048 KB Output is correct
2 Correct 1311 ms 6352 KB Output is correct
3 Correct 1797 ms 9040 KB Output is correct
4 Correct 316 ms 4328 KB Output is correct
5 Correct 482 ms 6392 KB Output is correct
6 Correct 695 ms 6548 KB Output is correct
7 Correct 809 ms 7236 KB Output is correct
8 Correct 1174 ms 14640 KB Output is correct
9 Correct 2224 ms 21352 KB Output is correct
10 Correct 3626 ms 27644 KB Output is correct
11 Correct 3739 ms 26648 KB Output is correct
12 Correct 4127 ms 21164 KB Output is correct
13 Correct 5018 ms 23128 KB Output is correct
14 Correct 6076 ms 24764 KB Output is correct
15 Correct 7160 ms 30748 KB Output is correct
16 Correct 7656 ms 34580 KB Output is correct
17 Correct 6120 ms 33336 KB Output is correct