Submission #492756

#	Time	Username	Problem	Language	Result	Execution time	Memory
492756		nickmet2004	Ball Machine (BOI13_ballmachine)	C++11	100 / 100	302 ms	27956 KiB

ballmachine

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int n , q;
vector<int> adj[N];
int S[N] , P[N][20] , R , A[N] , B[N] ,C[N], b;
void dfs(int u, int p){
    S[u]=u;
    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]){
        dfs(v,u);
        S[u] = min(S[u], S[v]);
    }
}
void DFS(int u){
    for(int v : adj[u]) DFS(v);
    B[++b] = u;
}
bool cmp(int a, int b){
    return S[a] < S[b];
}
int k = 0;
int Q(int u){
    for(int i = 17; ~i; --i){
        int y = P[u][i];
        if(C[y]) u = y ,k += (1 <<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;
        else adj[a].emplace_back(i);
    }
    for(int i = 1;i <= n; ++i) S[i] = 2e9;
    dfs(R,0);
    for(int i= 1; i<= n; ++i)sort(adj[i].begin() ,adj[i].end() , cmp);
    DFS(R);
    //for(int i = 1; i<= n; ++i)cout << B[i] << " ";cout << endl;
    for(int i = 1; i <= n; ++i) A[B[i]] = i;
    set<int> s;
    for(int i = 1; i<= n; ++i)s.insert(i);
    while(q--){
        int d;
        cin >> d;
        if(d==1){
            int x;
            cin >> x;
            int g = 0;
            while(x--){
                g = *s.begin();
                s.erase(s.begin());
                C[B[g]] =1;
            }
            cout << B[g]<<endl;
        }else{
            int u; cin>>u;
            int h = Q(u);
            cout << k << endl;k=0;
            s.insert(A[h]);
            C[h]=0;
        }
    }

return 0;
}

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