Submission #159677

#	Time	Username	Problem	Language	Result	Execution time	Memory
159677		Rouge_Hugo	Ball Machine (BOI13_ballmachine)	C++14	95.71 / 100	541 ms	33784 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;
set <pair<int,int>>s;
const int N=1e5+10;
vector<int>v1[N];
vector<pair<int,int>>v[N];
int n,q,lev[N],t[N],pa[N][25],yes[N];
void dfs (int x,int p)
{
    pa[x][0]=p;
    lev[x]=lev[p]+1;
    for(int i=1;i<22;i++)
    {
        pa[x][i]=pa[pa[x][i-1]][i-1];
    }
    for(auto it:v[x])
    {
        dfs(it.second,x);
    }
    t[x]=s.size();
    s.insert({t[x],x});
}
void add (int x)
{
    pair<int,int>last;
    while (x--)
    {
        last=*s.begin();
        yes[last.second]=1;
        s.erase(s.begin());
    }
    cout<<last.second<<endl;
}
void del(int x)
{
    int xx=x;
    for(int i=22;i>-1;i--)
    {
        if (yes[pa[xx][i]]==1)
            xx=pa[xx][i];
    }
    cout<<lev[x]-lev[xx]<<endl;
yes[xx]=0;
s.insert({t[xx],xx});
}
int dfs1 (int x,int p)
{
    int mn=x;
    for(auto it:v1[x])
    {
        mn=min(mn,dfs1(it,x));
    }
    v[p].push_back({mn,x});
    return mn;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int x;
    int root =1;
    cin>>n>>q;
    for(int i=1;i<n+1;i++)
    {
        cin>>x;
        if (x==0)
        {
            root=i;
            continue;
        }
        v1[x].push_back(i);
    }
    dfs1(root,0);
    for(int i=1;i<n;i++)
        sort(v[i].begin(),v[i].end());
    dfs (root,0);
    while (q--)
    {
        cin>>x;
        if (x==1)
        {
            cin>>x;
            add(x);

        }
        else {
            cin>>x;
            del(x);
        }
    }
}

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