oj.uz

Submission #754537

# Submission time Handle Problem Language Result Execution time Memory
754537 2023-06-08T00:16:10 Z asdfgrace Regions (IOI09_regions) C++17
95 / 100
 8000 ms 22536 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;

  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;
      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);
      }
      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:63:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |       for (int j = 0; j < at[i].size(); ++j) {
      |                       ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 19 ms 592 KB Output is correct
7 Correct 37 ms 464 KB Output is correct
8 Correct 28 ms 640 KB Output is correct
9 Correct 78 ms 1252 KB Output is correct
10 Correct 193 ms 1840 KB Output is correct
11 Correct 193 ms 1876 KB Output is correct
12 Correct 306 ms 2956 KB Output is correct
13 Correct 391 ms 2476 KB Output is correct
14 Correct 303 ms 2924 KB Output is correct
15 Correct 374 ms 5080 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 945 ms 7052 KB Output is correct
2 Correct 1256 ms 6352 KB Output is correct
3 Correct 1483 ms 9040 KB Output is correct
4 Correct 247 ms 2640 KB Output is correct
5 Correct 279 ms 4152 KB Output is correct
6 Correct 942 ms 4556 KB Output is correct
7 Correct 1126 ms 6048 KB Output is correct
8 Correct 1002 ms 10624 KB Output is correct
9 Correct 1904 ms 13208 KB Output is correct
10 Correct 3465 ms 17484 KB Output is correct
11 Correct 3260 ms 14776 KB Output is correct
12 Correct 4050 ms 16028 KB Output is correct
13 Correct 5055 ms 15924 KB Output is correct
14 Correct 6280 ms 16156 KB Output is correct
15 Correct 6832 ms 19264 KB Output is correct
16 Correct 7800 ms 22536 KB Output is correct
17 Execution timed out 8028 ms 21712 KB Time limit exceeded