oj.uz

Submission #310726

# Submission time Handle Problem Language Result Execution time Memory
310726 2020-10-07T17:45:25 Z VROOM_VARUN Ball Machine (BOI13_ballmachine) C++14
100 / 100
 351 ms 37172 KB 
/*
ID: varunra2
LANG: C++
TASK: ballmachine
*/

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

int n, q;
const int siz = 20;
VI par;
VVI adj;
VI mn;
VI d;
VVI lca;
VI ord;
vector<bool> vis;
int root = 0;

void init() {
  par.resize(n);
  adj.resize(n);
  mn.resize(n);
  d.resize(n);
  lca.resize(n);
  vis.assign(n, false);
  for (int i = 0; i < n; i++) {
    lca[i].resize(siz);
  }
}

void dfs1(int u, int v) {
  lca[u][0] = v;
  for (int i = 1; i < siz; i++) {
    int to = lca[u][i - 1];
    if (to == -1)
      lca[u][i] = -1;
    else
      lca[u][i] = lca[to][i - 1];
  }
  mn[u] = u;
  for (auto& x : adj[u]) {
    if (x == v) continue;
    d[x] = d[u] + 1;
    dfs1(x, u);
    mn[u] = min(mn[u], mn[x]);
  }
}

void dfs2(int u, int v) {
  VII frst;
  trav(x, adj[u]) {
    if (x == v) continue;
    frst.PB(MP(mn[x], x));
  }

  sort(all(frst));

  trav(x, frst) { dfs2(x.y, u); }
  ord.PB(u);
}

int main() {
// #ifndef ONLINE_JUDGE
  // freopen("ballmachine.in", "r", stdin);
  // freopen("ballmachine.out", "w", stdout);
// #endif
  cin.sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> q;

  init();

  for (int i = 0; i < n; i++) {
    cin >> par[i];
    par[i]--;
  }

  root = min_element(all(par)) - par.begin();

  for (int i = 0; i < n; i++) {
    if (~par[i]) {
      adj[i].PB(par[i]);
      adj[par[i]].PB(i);
    }
  }

  dfs1(root, -1);
  dfs2(root, -1);

  set<PII> empt;
  // set<PII> use;

  VI to(n);
  rep(i, 0, n) { to[ord[i]] = i; }

  for (int i = 0; i < n; i++) {
    empt.insert(MP(i, ord[i]));
  }


  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int k;
      cin >> k;
      int lst;
      while (k--) {
        // we need to insert a ball
        auto it = empt.begin();
        PII cur = *it;
        empt.erase(it);
        lst = cur.y;
        vis[lst] = true;
      }
      cout << lst + 1 << '\n';
    } else {
      int u;
      cin >> u;
      u--;
      int ret = 0;
      for (int i = siz - 1; i >= 0; i--) {
        if (lca[u][i] != -1 and vis[lca[u][i]]) {
          ret += (1 << i);
          u = lca[u][i];
        }
      }
      cout << ret << '\n';
      vis[u] = false;
      empt.insert(MP(to[u], u));
    }
  }

  return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:164:26: warning: 'lst' may be used uninitialized in this function [-Wmaybe-uninitialized]
  164 |       cout << lst + 1 << '\n';
      |                          ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 161 ms 17524 KB Output is correct
3 Correct 107 ms 17400 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 8 ms 1408 KB Output is correct
10 Correct 28 ms 4480 KB Output is correct
11 Correct 169 ms 17400 KB Output is correct
12 Correct 103 ms 17400 KB Output is correct
13 Correct 138 ms 17400 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7544 KB Output is correct
2 Correct 269 ms 31304 KB Output is correct
3 Correct 134 ms 25708 KB Output is correct
4 Correct 89 ms 10072 KB Output is correct
5 Correct 96 ms 10080 KB Output is correct
6 Correct 84 ms 10080 KB Output is correct
7 Correct 86 ms 8568 KB Output is correct
8 Correct 48 ms 7552 KB Output is correct
9 Correct 235 ms 31472 KB Output is correct
10 Correct 270 ms 31524 KB Output is correct
11 Correct 244 ms 31520 KB Output is correct
12 Correct 248 ms 27952 KB Output is correct
13 Correct 204 ms 32756 KB Output is correct
14 Correct 128 ms 25576 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 15976 KB Output is correct
2 Correct 308 ms 28844 KB Output is correct
3 Correct 215 ms 29684 KB Output is correct
4 Correct 187 ms 25208 KB Output is correct
5 Correct 202 ms 25248 KB Output is correct
6 Correct 200 ms 25252 KB Output is correct
7 Correct 202 ms 22992 KB Output is correct
8 Correct 227 ms 29664 KB Output is correct
9 Correct 288 ms 31604 KB Output is correct
10 Correct 305 ms 31776 KB Output is correct
11 Correct 305 ms 31528 KB Output is correct
12 Correct 307 ms 28732 KB Output is correct
13 Correct 351 ms 37172 KB Output is correct
14 Correct 208 ms 26144 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 31708 KB Output is correct
2 Correct 306 ms 28732 KB Output is correct
3 Correct 224 ms 36880 KB Output is correct
4 Correct 269 ms 31816 KB Output is correct
5 Correct 310 ms 31520 KB Output is correct
6 Correct 262 ms 31524 KB Output is correct
7 Correct 297 ms 28732 KB Output is correct
8 Correct 250 ms 36852 KB Output is correct
9 Correct 134 ms 25704 KB Output is correct