Submission #491224

#	Time	Username	Problem	Language	Result	Execution time	Memory
491224		nickmet2004	Ball Machine (BOI13_ballmachine)	C++11	0 / 100	276 ms	22512 KiB

ballmachine

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int n , q , A[N],B[N];
vector<int> adj[N] , v;
int P[N][20] , d[N] ,X[N];
int k,R;
void dfs(int u , int p){
    P[u][0] = p;
    for(int i = 1; i <= 18; ++i) P[u][i] = P[P[u][i-  1]][i-  1];
    for(int v : adj[u]){
        d[v] = d[u] + 1;
        dfs(v,u);
    }
    v.emplace_back(u);
}
int F(int u){
    for(int i = 17; ~i; --i){
        int y= P[u][i];
        if(A[y] <=k&& X[y]==0) u = P[u][i];
    }
    return u;
}
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n>>q;
    int a;
    for(int i = 1; i<= n; ++i){
        cin >> a;
        if(a==0)R = i;
        if(a)adj[a].emplace_back(i);
    }
    for(int i = 1; i <= n; ++i)sort(adj[i].begin() , adj[i].end());
    dfs(R,0);
    //for(int x : v)cout << x << " ";cout << endl;
    for(int i = 0; i < v.size(); ++i) A[v[i]] = i+1 , B[i + 1] = v[i];
    int t;
    queue<int> Q;
    while(q--){
        cin >> t;
        if(t==1){
            int j; cin >> j;
            while(j&&Q.size()){
                X[Q.front()] = 0;
                Q.pop();j--;
            }
            k+=j;
            //cout << k << "k "<<endl;
            cout << B[k] << endl;
        }else{
            int h; cin >> h;
            int v = F(h);
           // cout << v << "v"<<endl;
            Q.push(v);
            X[v]=-1;k--;
            cout << d[h] - d[v]<<endl;
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0; i < v.size(); ++i) A[v[i]] = i+1 , B[i + 1] = v[i];
      |                    ~~^~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40
• Subtask 4: 0 / 5