Submission #359332

#	Time	Username	Problem	Language	Result	Execution time	Memory
359332		Ahmad_Hasan	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	296 ms	28408 KiB

ballmachine

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

int n;
vector<vector<int> >adj;
vector<vector<int> >prnt;
vector<int>mins;
int rot;
int l;
int dfs1(int cr=rot,int p=0){
    prnt[cr][0]=p;
    for(int i=1;i<=l;i++){
        prnt[cr][i]=prnt[prnt[cr][i-1]][i-1];
    }
    int mn=cr;
    for(int i=0;i<adj[cr].size();i++){
        mn=min(mn,dfs1(adj[cr][i],cr));
    }

    return mins[cr]=mn;
}

vector<int>order;

bool comp(int x,int y){
    return mins[x]<mins[y];
}

void dfs2(int cr=rot){
    int mn=cr;
    sort(adj[cr].begin(),adj[cr].end(),comp);
    for(int i=0;i<adj[cr].size();i++){
        dfs2(adj[cr][i]);
    }

    order.push_back(cr);
}

vector<int>vis;

pair<int,int> findpr(int x){
    int cnt=0;
    for(int i=l;i>=0;i--){
        if(vis[prnt[x][i]]){
            x=prnt[x][i];
            cnt+=(1<<i);
        }

    }

    return {x,cnt};
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int q;
    cin>>n>>q;
    adj=vector<vector<int> >(n+5);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x)
            adj[x].push_back(i);
        else
            rot=i;
    }
    vis=mins=vector<int>(n+5);
    l=log2(n)+1;
    prnt=vector<vector<int> >(n+5,vector<int>(l+5,0));
    dfs1();
    dfs2();

    priority_queue<pair<int,int> >pq;
    vector<int>num(n+5);
    for(int i=0;i<order.size();i++){
        pq.push({-i,order[i]});
        num[order[i]]=i;
    }
    /**for(int i=1;i<=n;i++){
        cout<<i<<':';
        for(int j=0;j<=l;j++){
            cout<<prnt[i][j]<<' ';
        }
        cout<<'\n';
    }*/
    while(q--){
        int t,x;
        cin>>t>>x;
        if(t==1){
            for(int i=0;i<x;i++){
                pair<int,int>p=pq.top();   pq.pop();
                p.first*=-1;
                if(i==x-1)
                    cout<<p.second<<'\n';
                vis[p.second]=1;
            }

        }else{

            pair<int,int> p=findpr(x);
            vis[p.first]=0;
            cout<<p.second<<'\n';
            pq.push({-num[p.first],p.first});
        }

    }


    return 0;
}
/**
7
2 4 6 1 3 5 7
6
3 6 4 5 1 2
*/

Compilation message (stderr)

ballmachine.cpp: In function 'int dfs1(int, int)':
ballmachine.cpp:16:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=0;i<adj[cr].size();i++){
      |                 ~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs2(int)':
ballmachine.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<adj[cr].size();i++){
      |                 ~^~~~~~~~~~~~~~~
ballmachine.cpp:30:9: warning: unused variable 'mn' [-Wunused-variable]
   30 |     int mn=cr;
      |         ^~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<order.size();i++){
      |                 ~^~~~~~~~~~~~~

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