Submission #132823

#	Time	Username	Problem	Language	Result	Execution time	Memory
132823		muradeyn	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	189 ms	24428 KiB

ballmachine

/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define fyck ios_base::sync_with_stdio(0);cin.tie(0);
#define F first
#define S second
#define endl '\n'

using namespace std;

const int maxx = 100005 , lg = 17;

int n , q , x , ty , k , rt , nxt;

int par[maxx][lg] , dp[maxx] , used[maxx] , key[maxx];

bool cmp(int i,int j) {
    return dp[i] < dp[j];
}

vector<int>v[maxx];

priority_queue< pair<int,int> >pq;

void dfs(int s) {
    dp[s] = s;
    for (int to : v[s])dfs(to) , dp[s] = min(dp[s] , dp[to]);
    sort(v[s].begin(),v[s].end(),cmp);
}

void gen(int s) {
    for (int to : v[s])gen(to);
    key[s] = nxt--;
    pq.push({key[s] , s});
}

int main() {
    fyck
    cin>>n>>q;
    for (int i = 1;i<=n;i++) {
        cin>>x;
        if (x) {
            v[x].push_back(i);
            par[i][0] = x;
        }
        else rt = i;
    }
    for (int j = 1;j<lg;j++)
        for (int i = 1;i<=n;i++)
            par[i][j] = par[par[i][j - 1]][j - 1];
    dfs(rt);
    gen(rt);
    while (q--) {
        cin>>ty>>k;
        if (ty == 1) {
            while(k--) {
                x = pq.top().S;
                pq.pop();
                used[x] = 1;
            }
            cout<<x<<endl;
        }
        else {
            int res = 0;
            for (int i = lg - 1;i>=0;i--) {
                if (used[par[k][i]]) {
                    res += (1 << i);
                    k = par[k][i];
                }
            }
            cout<<res<<endl;
            used[k] = 0;
            pq.push({key[k] , k});
        }
    }
}

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