Submission #884640

#	Time	Username	Problem	Language	Result	Execution time	Memory
884640		AndreiBOTO	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	143 ms	79408 KiB

ballmachine

#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

const int NMAX=5e5+5;

priority_queue<pair<int,int> , vector<pair<int,int>>, greater<pair<int,int>>>pq;
vector<int>v[NMAX];
int asc[25][NMAX];
bool viz[NMAX];
int dp[NMAX];
int ti[NMAX];
int to[NMAX];
int kon;

bool cmp(int x,int y)
{
    return dp[x]<dp[y];
}

void dfs1(int p,int tata)
{
    dp[p]=p;
    for(int i=1;i<=24;i++)
        asc[i][p]=asc[i-1][asc[i-1][p]];
    for(auto i:v[p])
    {
        if(i!=tata)
        {
            asc[0][i]=p;
            dfs1(i,p);
            dp[p]=min(dp[p],dp[i]);
        }
    }
}

void dfs2(int p,int tata)
{
    sort(v[p].begin(),v[p].end(),cmp);
    for(auto i:v[p])
    {
        if(i!=tata)
            dfs2(i,p);
    }
    to[p]=++kon;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,q,i,j,root=-1;
    cin>>n>>q;
    for(i=1;i<=n;i++)
    {
        int x,y;
        cin>>x;
        if(x==0)
            root=i;
        else
        {
            v[x].push_back(i);
            v[i].push_back(x);
        }
    }
    dfs1(root,0);
    dfs2(root,0);
    for(i=1;i<=n;i++)
        pq.push(make_pair(to[i],i));
    while(q--)
    {
        int type,x;
        cin>>type>>x;
        if(type==1)
        {
            int best=-1;
            for(i=1;i<=x;i++)
            {
                int p=pq.top().second;
                pq.pop();
                best=p;
                viz[p]=true;
            }
            cout<<best<<"\n";
        }
        else
        {
            int kon=0;
            int p=x;
            for(int e=24;e>=0;e--)
                if(viz[asc[e][p]])
                {
                    kon+=(1<<e);
                    p=asc[e][p];
                }
            viz[p]=false;
            pq.push(make_pair(to[p],p));
            cout<<kon<<"\n";
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp:3: warning: ignoring '#pragma optimize GCC' [-Wunknown-pragmas]
    3 | #pragma optimize GCC ("Ofast")
      | 
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:65:15: warning: unused variable 'y' [-Wunused-variable]
   65 |         int x,y;
      |               ^
ballmachine.cpp:61:15: warning: unused variable 'j' [-Wunused-variable]
   61 |     int n,q,i,j,root=-1;
      |               ^

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