Submission #786938

#	Time	Username	Problem	Language	Result	Execution time	Memory
786938		n1427	Ball Machine (BOI13_ballmachine)	C++17	16.11 / 100	160 ms	27996 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

int n, q, root, timer = 0;
vector<int> parent, depth, subtreeMin, subtreeSize, timeIn;
vector<vector<int>> ancestor;
vector<vector<int>> adjList;
vector<pair<int, int>> queries;

vector<bool> colour;
priority_queue<pair<int, int>> whiteNodes;

void depthFirstSearchA(const int& u)
{
    subtreeMin[u] = u;
    subtreeSize[u] = 1;
    
    for (auto &v : adjList[u])
    {
        depth[v] = depth[u] + 1;
        ancestor[v][0] = u;
        for (int b = 1; ancestor[v][b - 1] != -1; b++)
            ancestor[v][b] = ancestor[ancestor[v][b - 1]][b - 1];
        depthFirstSearchA(v);
        subtreeMin[u] = min(subtreeMin[v], subtreeMin[u]);
        subtreeSize[u] += subtreeSize[v];
    }
    
    sort(adjList[u].begin(), adjList[u].end(), [&](const int& v1, const int& v2) -> bool
    {
        return subtreeMin[v1] < subtreeMin[v2];
    });
}

void depthFirstSearchB(const int& u)
{
    timeIn[u] = timer++;
    whiteNodes.push({timeIn[u], u});
    for (auto &v : adjList[u])
        depthFirstSearchB(v);
}

int main()
{
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);

    ios::sync_with_stdio(false);

    cin >> n >> q;
    adjList.resize(n + 1);
    parent.resize(n + 1);
    for (int u = 1; u <= n; u++)
    {
        cin >> parent[u];
        if (parent[u] == 0)
            root = u;
        else
            adjList[parent[u]].push_back(u);
    }

    depth.resize(n + 1);
    subtreeMin.resize(n + 1);
    subtreeSize.resize(n + 1);
    timeIn.resize(n + 1);
    ancestor.resize(n + 1, vector<int>(20, -1));
    depthFirstSearchA(root);
    depthFirstSearchB(root);
    
    queries.resize(q);
    for (int i = 0; i < q; i++)
        cin >> queries[i].first >> queries[i].second;

    colour.resize(n + 1);

    for (auto &query : queries)
    {
        int type = query.first, x = query.second;

        if (type == 1)
        {
            int u = -1;
            while (x --> 0)
            {
                u = whiteNodes.top().second;
                whiteNodes.pop();
                colour[u] = true;
            }
            cout << u << '\n';
        }

        if (type == 2)
        {
            int v = x;
            for (int b = 19; b >= 0; b--)
                if (ancestor[v][b] != -1)
                    if (colour[ancestor[v][b]])
                        v = ancestor[v][b];

            cout << depth[x] - depth[v] << '\n';
            colour[v] = false;
            whiteNodes.push({timeIn[v], v});
        }
    }
}

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