oj.uz

Submission #520119

# Submission time Handle Problem Language Result Execution time Memory
520119 2022-01-28T12:52:01 Z arnav2004 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 212 ms 37004 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int LOG = 25;
int N,Q;
int subtree[100005];
vector<int> graph[100005];
int post[100005];
int depth[100005];
bool filled[100005];
int up[100005][LOG];
int timer = 0;
struct cmp{
  bool operator()(const int &a, const int &b){
    return post[a] > post[b];
  }
};
void dfs(int node, int par){
  subtree[node] = node;
  for(int v : graph[node]){
    if(v == par) continue;
    up[v][0] = node;
    depth[v] = depth[node] + 1;
    dfs(v, node);
    subtree[node] = min(subtree[node], subtree[v]);
  }
}
void post_order(int node, int par){
  for(int v : graph[node]){
    if(v != par)
      post_order(v, node);
  }
  post[node] = timer++;
}
void binary_lift(int node, int par){
  for(int j = 1; j < LOG; j++){
    for(int i = 0; i < N; i++)
      up[i][j] = up[up[i][j - 1]][j - 1];
  }
}
signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> Q;
  int root = -1;
  for(int i = 0; i < N; i++){
    subtree[i] = 100005;
    int x; cin >> x;
    x--;
    if(x == -1) root = i;
    else{
      graph[x].emplace_back(i);
      graph[i].emplace_back(x);
    }
  }
  assert(root != -1);
  depth[root] = 0;
  dfs(root, -1);
  up[root][0] = root;
  for(int i = 0; i < N; i++){
    sort(graph[i].begin(), graph[i].end(), [&](const int &x, const int &y){
      return subtree[x] < subtree[y];
    });
  }
  binary_lift(root, -1);
  post_order(root, -1);
  priority_queue<int, vector<int>, cmp> khaali;
  for(int i = 0; i < N; i++)
    khaali.push(i);
  while(Q--){
    int T,K; cin >> T >> K;
    if(T == 1){
      for(int j = 0; j < K; j++){
        int x = khaali.top();
        khaali.pop();
        filled[x] = true;
        if(j == K - 1) cout << x + 1 << '\n';
      }
    }
    else{
      K--;
      int pos = K;
      for(int i = LOG - 1; i >= 0; i--){
        if(filled[up[pos][i]])
        pos = up[pos][i];
      }
      filled[pos] = false;
      khaali.push(pos);
      cout << depth[K] - depth[pos] << '\n';
    }
  }
  return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 123 ms 20740 KB Output is correct
3 Correct 70 ms 20796 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2904 KB Output is correct
7 Correct 2 ms 2892 KB Output is correct
8 Correct 2 ms 2892 KB Output is correct
9 Correct 6 ms 3788 KB Output is correct
10 Correct 24 ms 7304 KB Output is correct
11 Correct 125 ms 20752 KB Output is correct
12 Correct 72 ms 20828 KB Output is correct
13 Correct 110 ms 20708 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 9124 KB Output is correct
2 Correct 168 ms 33244 KB Output is correct
3 Correct 101 ms 29340 KB Output is correct
4 Correct 63 ms 11988 KB Output is correct
5 Correct 70 ms 11996 KB Output is correct
6 Correct 61 ms 11968 KB Output is correct
7 Correct 67 ms 10712 KB Output is correct
8 Correct 36 ms 9240 KB Output is correct
9 Correct 164 ms 33084 KB Output is correct
10 Correct 172 ms 33328 KB Output is correct
11 Correct 152 ms 33332 KB Output is correct
12 Correct 157 ms 30696 KB Output is correct
13 Correct 117 ms 32852 KB Output is correct
14 Correct 101 ms 29340 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 18032 KB Output is correct
2 Correct 188 ms 31484 KB Output is correct
3 Correct 143 ms 30128 KB Output is correct
4 Correct 123 ms 27232 KB Output is correct
5 Correct 114 ms 27384 KB Output is correct
6 Correct 128 ms 27432 KB Output is correct
7 Correct 110 ms 25792 KB Output is correct
8 Correct 134 ms 30136 KB Output is correct
9 Correct 206 ms 33216 KB Output is correct
10 Correct 182 ms 33620 KB Output is correct
11 Correct 173 ms 33508 KB Output is correct
12 Correct 182 ms 31644 KB Output is correct
13 Correct 212 ms 37004 KB Output is correct
14 Correct 124 ms 29436 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 33496 KB Output is correct
2 Correct 193 ms 31528 KB Output is correct
3 Correct 113 ms 36808 KB Output is correct
4 Correct 177 ms 33396 KB Output is correct
5 Correct 177 ms 33412 KB Output is correct
6 Correct 142 ms 33396 KB Output is correct
7 Correct 194 ms 31444 KB Output is correct
8 Correct 130 ms 36772 KB Output is correct
9 Correct 94 ms 29436 KB Output is correct