Submission #491934

#	Time	Username	Problem	Language	Result	Execution time	Memory
491934		nickmet2004	Ball Machine (BOI13_ballmachine)	C++11	16.11 / 100	1096 ms	25604 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 mx;
int F(int u){
    for(int i = 17; ~i; --i){
        int y= P[u][i];
        if(X[y]==1&&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;
    set<int> free;
    for(int i= 1; i<= n; ++i)free.insert(i);
    while(q--){
        cin >> t;
        if(t==1){
            int k;
            cin >>k;
            int x;
            for(int i = 0; i < k; ++i){
                x = *free.begin();
                X[B[x]] = 1;
                free.erase(free.begin());
            }
            //cout << k << "k "<<endl;
            mx = max(mx , x);
            cout << B[mx] <<endl;
        }else{
            int h; cin >> h;
            int v = F(h);
            //cout << v << " v" << endl;
           // cout << v << "v"<<endl;
           if(mx==A[v])mx=0;
            free.insert(A[v]);
            X[v]=0;
            cout << d[h] - d[v]<<endl;
        }
    }
}

Compilation message (stderr)

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

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