oj.uz

Submission #520118

# Submission time Handle Problem Language Result Execution time Memory
520118 2022-01-28T12:49:29 Z arnav2004 Ball Machine (BOI13_ballmachine) C++17
22.4969 / 100
 230 ms 37060 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;
    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 v : graph[node]){
    if(v == par) continue;
    up[v][0] = node;
    for(int j = 1; j < LOG; j++)
      up[v][j] = up[up[v][j - 1]][j - 1];
    binary_lift(v, node);
  }
}
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
3.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Incorrect 124 ms 20740 KB Output isn't correct
3 Correct 92 ms 20912 KB Output is correct
4 Incorrect 2 ms 2636 KB Output isn't correct
5 Incorrect 2 ms 2636 KB Output isn't correct
6 Incorrect 2 ms 2892 KB Output isn't correct
7 Incorrect 2 ms 2892 KB Output isn't correct
8 Incorrect 3 ms 2892 KB Output isn't correct
9 Incorrect 7 ms 3788 KB Output isn't correct
10 Incorrect 21 ms 7256 KB Output isn't correct
11 Incorrect 123 ms 20744 KB Output isn't correct
12 Correct 80 ms 20828 KB Output is correct
13 Incorrect 101 ms 20668 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9180 KB Output is correct
2 Incorrect 213 ms 33324 KB Output isn't correct
3 Correct 93 ms 29244 KB Output is correct
4 Incorrect 67 ms 11936 KB Output isn't correct
5 Incorrect 68 ms 12052 KB Output isn't correct
6 Incorrect 64 ms 12108 KB Output isn't correct
7 Incorrect 64 ms 10804 KB Output isn't correct
8 Correct 37 ms 9188 KB Output is correct
9 Incorrect 176 ms 33204 KB Output isn't correct
10 Incorrect 212 ms 33456 KB Output isn't correct
11 Incorrect 199 ms 33288 KB Output isn't correct
12 Incorrect 186 ms 30728 KB Output isn't correct
13 Correct 140 ms 32880 KB Output is correct
14 Correct 93 ms 29344 KB Output is correct

Subtask #3
5.71428571429 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 18008 KB Output isn't correct
2 Incorrect 209 ms 31532 KB Output isn't correct
3 Correct 145 ms 30128 KB Output is correct
4 Incorrect 137 ms 27252 KB Output isn't correct
5 Incorrect 148 ms 27460 KB Output isn't correct
6 Incorrect 152 ms 27468 KB Output isn't correct
7 Incorrect 158 ms 25792 KB Output isn't correct
8 Correct 173 ms 30120 KB Output is correct
9 Incorrect 208 ms 33288 KB Output isn't correct
10 Incorrect 228 ms 33424 KB Output isn't correct
11 Incorrect 229 ms 33492 KB Output isn't correct
12 Incorrect 215 ms 31540 KB Output isn't correct
13 Incorrect 230 ms 37060 KB Output isn't correct
14 Incorrect 129 ms 29480 KB Output isn't correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 33408 KB Output isn't correct
2 Incorrect 208 ms 31472 KB Output isn't correct
3 Correct 177 ms 36744 KB Output is correct
4 Incorrect 223 ms 33496 KB Output isn't correct
5 Incorrect 215 ms 33412 KB Output isn't correct
6 Correct 191 ms 33616 KB Output is correct
7 Incorrect 224 ms 31540 KB Output isn't correct
8 Correct 163 ms 36848 KB Output is correct
9 Correct 92 ms 29376 KB Output is correct