oj.uz

Submission #303731

# Submission time Handle Problem Language Result Execution time Memory
303731 2020-09-20T15:27:23 Z quocnguyen1012 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 288 ms 30840 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

int N, Q, mn[maxn], pos[maxn], cnt, col[maxn], par[maxn][20];
vector<int> adj[maxn];

void dfs(int u) {
  for (int i = 1; i <= 19; ++i) {
    par[u][i] = par[par[u][i - 1]][i - 1];
  }
  mn[u] = u;
  for (int v : adj[u]) {
    par[v][0] = u;
    dfs(v);
    mn[u] = min(mn[u], mn[v]);
  }
}

void go(int u) {
  vector<ii> order;
  for (int v : adj[u]) {
    order.eb(mn[v], v);
  }
  sort(order.begin(), order.end());
  for (auto & v : order) {
    go(v.se);
  }
  pos[u] = ++cnt;
}

signed main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> Q;
  int root;
  for (int i = 1; i <= N; ++i) {
    int p; cin >> p;
    if (!p) root = i;
    else adj[p].eb(i);
  }
  dfs(root);
  go(root);
  set<ii> emp;
  for (int i = 1; i <= N; ++i) {
    emp.insert({pos[i], i});
  }
  while (Q--) {
    int type, x; cin >> type >> x;
    if (type == 1) {
      int res = 0;
      while (x--) {
        auto it = emp.begin();
        res = (*it).se;
        col[res] = 1;
        emp.erase(it);
      }
      cout << res << '\n';
    } else {
      int res = 0;
      for (int i = 18; i >= 0; --i) {
        if (col[par[x][i]]) {
          res += (1 << i);
          x = par[x][i];
        }
      }
      emp.insert(mp(pos[x], x));
      col[x] = 0;
      cout << res << '\n';
    }
  }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:57:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |   go(root);
      |   ~~^~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 151 ms 13988 KB Output is correct
3 Correct 92 ms 13816 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 9 ms 3456 KB Output is correct
10 Correct 26 ms 5504 KB Output is correct
11 Correct 156 ms 14072 KB Output is correct
12 Correct 93 ms 13980 KB Output is correct
13 Correct 132 ms 14072 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8184 KB Output is correct
2 Correct 252 ms 24772 KB Output is correct
3 Correct 111 ms 18532 KB Output is correct
4 Correct 86 ms 9892 KB Output is correct
5 Correct 114 ms 9720 KB Output is correct
6 Correct 74 ms 9848 KB Output is correct
7 Correct 75 ms 8568 KB Output is correct
8 Correct 41 ms 8184 KB Output is correct
9 Correct 217 ms 25048 KB Output is correct
10 Correct 233 ms 24824 KB Output is correct
11 Correct 194 ms 24696 KB Output is correct
12 Correct 216 ms 21880 KB Output is correct
13 Correct 173 ms 27000 KB Output is correct
14 Correct 107 ms 18464 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 13928 KB Output is correct
2 Correct 264 ms 22392 KB Output is correct
3 Correct 185 ms 24952 KB Output is correct
4 Correct 170 ms 20500 KB Output is correct
5 Correct 178 ms 20216 KB Output is correct
6 Correct 174 ms 20216 KB Output is correct
7 Correct 174 ms 18296 KB Output is correct
8 Correct 182 ms 24912 KB Output is correct
9 Correct 261 ms 25336 KB Output is correct
10 Correct 281 ms 24952 KB Output is correct
11 Correct 266 ms 24956 KB Output is correct
12 Correct 288 ms 22520 KB Output is correct
13 Correct 280 ms 30840 KB Output is correct
14 Correct 205 ms 19432 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 25304 KB Output is correct
2 Correct 273 ms 22548 KB Output is correct
3 Correct 188 ms 30072 KB Output is correct
4 Correct 249 ms 25436 KB Output is correct
5 Correct 262 ms 25084 KB Output is correct
6 Correct 212 ms 24952 KB Output is correct
7 Correct 252 ms 22392 KB Output is correct
8 Correct 189 ms 30204 KB Output is correct
9 Correct 112 ms 18536 KB Output is correct