Submission #1244267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244267		chikien2009	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	565 ms	32188 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

struct SEGMENT_TREE
{
    int tree[500000];
    inline void Update(int ind, int l, int r, int x, int v)
    {
        if (r < x || x < l)
        {
            return;
        }
        if (l == r)
        {
            tree[ind] += v;
            return;
        }
        int m = (l + r) >> 1;
        Update(ind << 1, l, m, x, v);
        Update(ind << 1 | 1, m + 1, r, x, v);
        tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
    }
    inline int Get(int ind, int l, int r, int x, int y)
    {
        if (r < x || y < l)
        {
            return 0;
        }
        if (x <= l && r <= y)
        {
            return tree[ind];
        }
        int m = (l + r) >> 1;
        return Get(ind << 1, l, m, x, y) + Get(ind << 1 | 1, m + 1, r, x, y);
    }
} st;

int n, q, a, b, root;
int mn[100000], id[100000], head[100000], tail[100000], sp[20][100000], depth[100000];
vector<int> g[100000];
priority_queue<pair<int, int>> pq;

inline void DFS1(int node)
{
    vector<pair<int, int>> v;
    mn[node] = node;
    for (int i = 1; i < 20; ++i)
    {
        sp[i][node] = sp[i - 1][sp[i - 1][node]];
    }
    for (auto &i : g[node])
    {
        sp[0][i] = node;
        depth[i] = depth[node] + 1;
        DFS1(i);
        v.push_back({mn[i], i});
        mn[node] = min(mn[node], mn[i]);
    }
    sort(v.begin(), v.end());
    g[node].clear();
    for (auto &i : v)
    {
        g[node].push_back(i.second);
    }
}

inline void DFS2(int node)
{
    head[node] = b++;
    for (auto &i : g[node])
    {
        DFS2(i);
    }
    id[node] = a++;
    tail[node] = b - 1;
    pq.push({-id[node], node});
}

int main()
{
    setup();

    cin >> n >> q;
    for (int i = 0; i < n; ++i)
    {
        cin >> a;
        if (a == 0)
        {
            root = i;
        }
        else
        {
            g[a - 1].push_back(i);
        }
    }
    a = 0;
    b = 1;
    sp[0][root] = root;
    DFS1(root);
    DFS2(root);
    while (q--)
    {
        cin >> a >> b;
        if (a == 1)
        {
            while (b > 0 && !pq.empty())
            {
                a = pq.top().second;
                st.Update(1, 1, n, head[a], 1);
                pq.pop();
                b--;
            }
            cout << a + 1 << "\n";
        }
        else
        {
            b--;
            a = b;
            for (int i = 19, j; i >= 0; --i)
            {
                j = sp[i][a];
                if (st.Get(1, 1, n, head[j], tail[j]) == tail[j] - head[j] + 1)
                {
                    a = j;
                }
            }
            st.Update(1, 1, n, head[a], -1);
            pq.push({-id[a], a});
            cout << depth[b] - depth[a] << "\n";
        }
    }
    return 0;
}

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