제출 #1192154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192154		maxFedorchuk	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	216 ms	26072 KiB

ballmachine

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

const long long MX=1e5+10,LG=20;

vector < int > mas[MX];

int st[MX],old_to_new[MX],new_to_old[MX];
int lca[LG][MX],mnprd[MX],depth[MX];

int get_lca(int a)
{
    for(int i=LG-1;i>=0;i--)
    {
        if(st[lca[i][a]])
        {
            a=lca[i][a];
        }
    }

    return a;
}

void DFS(int zar,int mun,int deep)
{
    depth[zar]=deep;

    lca[0][zar]=mun;
    for(int i=1;i<LG;i++)
    {
        lca[i][zar]=lca[i-1][lca[i-1][zar]];
    }

    mnprd[zar]=zar;
    for(auto u:mas[zar])
    {
        if(u!=mun)
        {
            DFS(u,zar,deep+1);
            mnprd[zar]=min(mnprd[u],mnprd[zar]);
        }
    }
}

int timer=0;

bool cmp(int a,int b)
{
    return (mnprd[a]<mnprd[b]);
}
void DFS2(int zar,int mun)
{
    sort(mas[zar].begin(),mas[zar].end(),cmp);
    for(auto u:mas[zar])
    {
        if(u!=mun)
        {
            DFS2(u,zar);
        }
    }

    timer++;
    old_to_new[zar]=timer;
    new_to_old[timer]=zar;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n,q;
    cin>>n>>q;

    int root;
    for(int i=1;i<=n;i++)
    {
        int a;
        cin>>a;

        if(a!=0)
        {
            mas[i].push_back(a);
            mas[a].push_back(i);
        }
        else
        {
            root=i;
        }
    }

    DFS(root,0,1);
    DFS2(root,0);

    priority_queue < int , vector < int > , greater < int > > qq;
    for(int i=1;i<=n;i++)
    {
        qq.push(i);
    }

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

        if(t==1)
        {
            int k,in;
            cin>>k;

            while(k--)
            {
                in=new_to_old[qq.top()];
                st[in]=1;
                qq.pop();
            }

            cout<<in<<"\n";
        }
        else
        {
            int in;
            cin>>in;

            int vr=get_lca(in);
            st[vr]=0;
            qq.push(old_to_new[vr]);

            cout<<depth[in]-depth[vr]<<"\n";
        }
    }

    return 0;
}

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