oj.uz

Submission #774762

# Submission time Handle Problem Language Result Execution time Memory
774762 2023-07-06T02:48:11 Z arush_agu Ball Machine (BOI13_ballmachine) C++17
100 / 100
 597 ms 27204 KB 
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#ifdef DEBUG
#include <time.h>
#endif

#define all(a) (a).begin(), (a).end()
#define rev(a) (a).rbegin(), (a).rend()
#define F first
#define S second
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                                 \
  {                                                                            \
    ++recur_depth;                                                             \
    auto x_ = x;                                                               \
    --recur_depth;                                                             \
    cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":"           \
         << __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl;         \
  }
#else
#define dbg(x)
#endif

using namespace std;
using namespace __gnu_pbds;

typedef pair<int, int> ii;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> llll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vii;
typedef vector<pair<int, ii>> viii;
typedef vector<vii> vvii;
typedef vector<viii> vviii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll, ll>> vll;
typedef vector<vll> vvll;

typedef vector<bool> vb;

template <class type1>
using ordered_set = tree<type1, null_type, less<type1>, rb_tree_tag,
                         tree_order_statistics_node_update>;

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e9;
const ld EPS = 1e-9;

const int MAXLG = 18;
const int MAXN = 1e5 + 1;
int n, q, root;
int par[MAXN], mn_subtree[MAXN], depth[MAXN], tin[MAXN], tout[MAXN],
    up[MAXLG][MAXN], cnt_cball[MAXN];
vi child[MAXN];
bool is_ball[MAXN], inq[MAXN];
int timer = 0;

// void f(int u, int p) {
//   tin[u] = ++timer;
//   mn_subtree[u] = u;
//   for (int &v : child[u]) {
//     depth[v] = depth[u] + 1;
//     f(v, u);
//     mn_subtree[u] = min(mn_subtree[u], mn_subtree[v]);
//   }
//   tout[u] = ++timer;
// }

void solve() {
  cin >> n >> q;
  for (int i = 0; i < n; ++i) {
    cin >> par[i];
    if (--par[i] == -1)
      root = i;
  }

  for (int i = 0; i < n; ++i)
    if (i != root)
      child[par[i]].push_back(i);

  depth[root] = 0;
  function<void(int, int)> f = [&](int u, int p) {
    tin[u] = ++timer;
    mn_subtree[u] = u;
    for (int &v : child[u]) {
      depth[v] = depth[u] + 1;
      f(v, u);
      mn_subtree[u] = min(mn_subtree[u], mn_subtree[v]);
    }
    tout[u] = ++timer;
  };
  f(root, -1);

  for (int i = 0; i < n; ++i)
    up[0][i] = par[i];

  for (int j = 1; j < MAXLG; ++j)
    for (int i = 0; i < n; ++i) {
      if (up[j - 1][i] != -1)
        up[j][i] = up[j - 1][up[j - 1][i]];
      else
        up[j][i] = -1;
    }

  auto is_anc = [&](int u, int v) {
    return tin[v] <= tin[u] && tout[u] <= tout[v];
  };

  auto kth_anc = [&](int u, int k) {
    for (int i = MAXLG - 1; i >= 0; --i)
      if (k & (1 << i)) {
        u = up[i][u];
      }
    return u;
  };

  auto just_lca = [&](int u, int v) -> ii {
    if (depth[u] > depth[v])
      u = kth_anc(u, depth[u] - depth[v]);
    else
      v = kth_anc(v, depth[v] - depth[u]);

    u = kth_anc(u, depth[u] - depth[v]);

    for (int i = MAXLG - 1; i >= 0; --i)
      if (up[i][u] != up[i][v]) {
        u = up[i][u];
        v = up[i][v];
      }

    return {u, v};
  };

  auto s_cmp = [&](int u, int v) -> bool {
    if (u == v)
      return 0;
    if (is_anc(u, v))
      return 0;
    if (is_anc(v, u))
      return 1;
    auto [x, y] = just_lca(u, v);
    return mn_subtree[x] > mn_subtree[y];
  };

  priority_queue<int, vi, decltype(s_cmp)> s(s_cmp);
  for (int i = 0; i < n; ++i)
    if (child[i].empty())
      s.push(i), inq[i] = 1;

  while (q--) {
    int t, x;
    cin >> t >> x;

    if (t == 1) {
      for (int i = 1; i <= x; ++i) {
        int u = s.top();
        s.pop();

        inq[u] = 0;
        is_ball[u] = 1;

        if (u != root)
          if (++cnt_cball[par[u]] == child[par[u]].size() && !inq[par[u]])
            s.push(par[u]), inq[par[u]] = 1;

        if (i == x)
          cout << u + 1 << "\n";
      }
    } else {
      --x;
      int ans = x;
      for (int i = MAXLG - 1; i >= 0; i--)
        if (up[i][ans] != -1 && is_ball[up[i][ans]])
          ans = up[i][ans];

      is_ball[ans] = 0;
      if (ans != root)
        cnt_cball[par[ans]]--;
      if (!inq[ans])
        s.push(ans), inq[ans] = 1;

      cout << depth[x] - depth[ans] << "\n";
    }
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);

  clock_t start = clock();

  int test_cases = 1;
  // cin >> test_cases;

  while (test_cases--)
    solve();

#ifdef DEBUG
  cerr << fixed << setprecision(10)
       << "\nTime Taken: " << (double)(clock() - start) / CLOCKS_PER_SEC
       << "s\n";
#endif
  return 0;
}

Compilation message

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:207:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |           if (++cnt_cball[par[u]] == child[par[u]].size() && !inq[par[u]])
      |               ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:235:11: warning: unused variable 'start' [-Wunused-variable]
  235 |   clock_t start = clock();
      |           ^~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 343 ms 11636 KB Output is correct
3 Correct 161 ms 11368 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 3 ms 2900 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 3 ms 2824 KB Output is correct
9 Correct 19 ms 3284 KB Output is correct
10 Correct 64 ms 4956 KB Output is correct
11 Correct 327 ms 11748 KB Output is correct
12 Correct 153 ms 11384 KB Output is correct
13 Correct 348 ms 11668 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 7508 KB Output is correct
2 Correct 535 ms 20848 KB Output is correct
3 Correct 181 ms 14808 KB Output is correct
4 Correct 179 ms 8908 KB Output is correct
5 Correct 211 ms 8780 KB Output is correct
6 Correct 199 ms 8636 KB Output is correct
7 Correct 244 ms 7736 KB Output is correct
8 Correct 21 ms 7508 KB Output is correct
9 Correct 288 ms 21420 KB Output is correct
10 Correct 553 ms 20920 KB Output is correct
11 Correct 363 ms 20700 KB Output is correct
12 Correct 542 ms 18180 KB Output is correct
13 Correct 44 ms 23244 KB Output is correct
14 Correct 151 ms 14708 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 12208 KB Output is correct
2 Correct 460 ms 18736 KB Output is correct
3 Correct 61 ms 21952 KB Output is correct
4 Correct 227 ms 17820 KB Output is correct
5 Correct 273 ms 17416 KB Output is correct
6 Correct 265 ms 17524 KB Output is correct
7 Correct 281 ms 15564 KB Output is correct
8 Correct 59 ms 22044 KB Output is correct
9 Correct 362 ms 21496 KB Output is correct
10 Correct 431 ms 21032 KB Output is correct
11 Correct 450 ms 21192 KB Output is correct
12 Correct 466 ms 18764 KB Output is correct
13 Correct 107 ms 27204 KB Output is correct
14 Correct 283 ms 15724 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 21580 KB Output is correct
2 Correct 516 ms 18640 KB Output is correct
3 Correct 69 ms 25648 KB Output is correct
4 Correct 403 ms 21608 KB Output is correct
5 Correct 597 ms 20976 KB Output is correct
6 Correct 404 ms 20812 KB Output is correct
7 Correct 523 ms 18616 KB Output is correct
8 Correct 59 ms 25764 KB Output is correct
9 Correct 158 ms 14796 KB Output is correct