Submission #385630

#	Time	Username	Problem	Language	Result	Execution time	Memory
385630		blue	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	570 ms	25836 KiB

ballmachine

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
int Q;
int r;

int anc[100001][19];
vector<int> children[100001];
vector<int> subtree(100001, 0);
vector<int> height(100001, 0);
vector<int> mindes(100001, 1e9);

vector<int> occ(100001, 0);
vector<int> occ_bit(100001, 0);
vector<int> order_ind(100001);
vector<int> order(1, 0);




void dfs1(int u)
{
    subtree[u] = 1;
    mindes[u] = u;

    for(int e = 1; e <= 18; e++) anc[u][e] = anc[ anc[u][e-1] ][e-1];

    for(int v: children[u])
    {
        height[v] = height[u] + 1;
        dfs1(v);
        subtree[u] += subtree[v];
        mindes[u] = min(mindes[u], mindes[v]);
    }
}





void dfs2(int u)
{
    for(int v: children[u]) dfs2(v);
    order_ind[u] = order.size();
    order.push_back(u);
}


int insert(int l, int r)
{
    if(l == r)
    {
        occ[ order[l] ] = 1;
        for(int i = l; i <= N; i += i&-i) occ_bit[i]++;
        return order[l];
    }

    int m = (l+r)/2;
    int s = 0;
    for(int i = m; i >= 1; i -= i&-i) s += occ_bit[i];
    if(s < m) return insert(l, m);
    else return insert(m+1, r);
}


int erase(int v)
{
    int a = v;
    for(int i = 18; i >= 0; i--)
    {
        if(occ[ anc[a][i] ]) a = anc[a][i];
    }

    occ[a] = 0;
    for(int i = order_ind[a]; i <= N; i += i&-i) occ_bit[i]--;

    return(height[v] - height[a]);
}


int main()
{
    cin >> N >> Q;

    anc[0][0] = 0;
    for(int i = 1; i <= N; i++)
    {
        cin >> anc[i][0];
        children[ anc[i][0] ].push_back(i);
        if(anc[i][0] == 0) r = i;
    }

    dfs1(r);

    for(int i = 1; i <= N; i++)
        sort(children[i].begin(), children[i].end(),
            [] (int x, int y)
            {
                return mindes[x] < mindes[y];
            }
        );

    dfs2(r);

    while(Q--)
    {
        int t;
        cin >> t;


        if(t == 1)
        {
            int x;
            cin >> x;

            for(int i = 1; i <= x-1; i++) insert(1, N);
            cout << insert(1, N) << '\n';
        }

        else
        {
            int v;
            cin >> v;
            cout << erase(v) << '\n';
        }
    }
}

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