Submission #493174

#	Time	Username	Problem	Language	Result	Execution time	Memory
493174		Rainbowbunny	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	164 ms	25440 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
const int MAXL = 20;

int n, q, Time, r;
int mn[MAXN], e[MAXN], tout[MAXN], up[MAXN][MAXL], H[MAXN];
bool In[MAXN];
priority_queue <int, vector <int>, greater <int> > pq;
vector <int> Adj[MAXN];

void DFS1(int node)
{
    mn[node] = node;
    for(auto x : Adj[node])
    {
        DFS1(x);
        mn[node] = min(mn[node], mn[x]);
    }
}

void DFS2(int node, int p)
{
    sort(Adj[node].begin(), Adj[node].end(), [](int x, int y)
    {
        return mn[x] < mn[y];
    });
    up[node][0] = p;
    for(int i = 1; i < MAXL; i++)
    {
        up[node][i] = up[up[node][i - 1]][i - 1];
    }
    for(auto x : Adj[node])
    {
        H[x] = H[node] + 1;
        DFS2(x, node);
    }
    Time++;
    e[Time] = node;
    tout[node] = Time;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        int id;
        cin >> id;
        if(id)
        {
            Adj[id].push_back(i);
        }
        else
        {
            r = i;
        }
    }
    DFS1(r);
    DFS2(r, r);
    for(int i = 1; i <= Time; i++)
    {
        pq.emplace(i);
    }
    while(q--)
    {
        int Type;
        cin >> Type;
        if(Type == 1)
        {
            int k, lst;
            cin >> k;
            for(int i = 1; i <= k; i++)
            {
                In[e[pq.top()]] = true;
                lst = e[pq.top()];
                pq.pop();
            }
            cout << lst << '\n';
        }
        else
        {
            int k;
            cin >> k;
            int ii = k;
            for(int i = MAXL - 1; i >= 0; i--)
            {
                if(In[up[ii][i]])
                {
                    ii = up[ii][i];
                }
            }
            cout << H[k] - H[ii] << '\n';
            In[ii] = false;
            pq.push(tout[ii]);
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:83:28: warning: 'lst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |             cout << lst << '\n';
      |                            ^~~~

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