Submission #763602

#	Time	Username	Problem	Language	Result	Execution time	Memory
763602		Ellinor	Ball Machine (BOI13_ballmachine)	C++14	48.05 / 100	1089 ms	28448 KiB

ballmachine

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

#define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
typedef long long ll;

// inlinevoid fastIO() { using stdio cin.tie(NULL); cout.tie(NULL); }

int N,Q;
int a;
vector<int> pars;
vector<vector<int>> kids;
vector<int> min_in_subtree;
vector<int> next_kid;

int find_min_in_subtree(int node){
    //cerr<<"node: "<<node<<"\n";
    int ret=node;
    rep(i,0,kids[node].size()){
        ret=min(ret,find_min_in_subtree(kids[node][i]));
    }
    min_in_subtree[node]=ret;
    //cerr<<"ret: "<<ret<<"\n";
    return ret;
}

// bool cmp(const Edge &x, const Edge &y) { return min_in_subtree[x]<min_in_subtree[y]; }

set<int> not_taken;
vector<int> take_order;
vector<bool> taken;//?

vector<int> i_take_me;

void order_dfs(int node){
    if(kids[node].size()){
        //
        rep(i,0,kids[node].size()){
            order_dfs(kids[node][i]);
        }
    }
    take_order.push_back(node);
    i_take_me[node] = take_order.size()-1;
}

vector<vector<int>> up;

void build_up(int node){
    //cerr<<node<<"\n";
    if(pars[node]==-1) up[node][0]=0;
    else up[node][0]=pars[node];
    rep(i,1,up[node].size()){
        up[node][i]=up[up[node][i-1]][i-1];
    }
    rep(i,0,kids[node].size()){
        build_up(kids[node][i]);
    }
}

int main()
{
    cin>>N>>Q;
    pars.assign(N,-1);
    kids.assign(N,{});
    int root;
    rep(i,0,N){
        //parents
        cin>>a;
        a--;
        pars[i] = a;
        if(a>=0)kids[a].push_back(i);
        else root=i;
    }

    i_take_me.assign(N,-1);

    // rep(i,0,pars.size()){
    //     cerr<<pars[i]<<" ";
    // }
    // cerr<<"\n";

    // rep(i,0,N){
    //     rep(j,0,kids[i].size()){
    //         cerr<<kids[i][j]<<" ";
    //     }
    //     cerr<<"\n";
    // }

    min_in_subtree.assign(N,-1);
    find_min_in_subtree(root);

    // rep(i,0,N){
    //     cerr<<min_in_subtree[i]<<" ";
    // }
    // cerr<<"\n";

    // next_kid.assign(N,-1);
    rep(i,0,N){
        if(kids[i].size()){
            vector<pair<int,int>> v;
            rep(j,0,kids[i].size()){
                v.push_back({min_in_subtree[kids[i][j]],kids[i][j]});
            }
            sort(v.begin(),v.end());
            kids[i]={};
            rep(j,0,v.size()){
                kids[i].push_back(v[j].second);
            }
        }
    }
    //kids sorted
    // rep(i,0,N){
    //     if(kids[i].size()){
    //         next_kid[i]=kids[i][0];
    //     }
    // }

    order_dfs(root);

    // taken, not_taken
    taken.assign(N,false);
    rep(i,0,N){
        not_taken.insert(i);
    }

    //
    //cerr<<"hi\n";
    up.assign(N, vector<int>(log2(N)+1, root));
    build_up(root);

    //
    // rep(i,0,N){
    //     rep(j,0,up[i].size()){
    //         cerr<<up[i][j]<<" ";
    //     }
    //     cerr<<"\n";
    // }

    //
    int q,k;
    rep(i,0,Q){
        cin>>q>>k;
        if(q==1){
            rep(j,0,k){
                auto x=not_taken.begin();
                int take= *x;
                not_taken.erase(x);
                taken[take_order[take]]=true;
                if(j==k-1){
                    cout<<take_order[take]+1<<"\n";//+1
                }
            }
        }
        else{//q==2
            int at=k-1;
            int ans=0;
            if(taken[up[at][0]]){
                while(true){
                    int low=0;
                    int high=log2(N)+1;//ex
                    int mid;
                    while(low+1<high){
                        mid=(low+high)/2;
                        if(taken[up[at][mid]] && up[at][mid]==root && mid != 0) high=mid;
                        else if(taken[up[at][mid]]) low=mid;
                        else high=mid;
                    }
                    ans+=pow(2,low);//??!
                    at=up[at][low];
                    if(!taken[up[at][0]] || at==root) break;
                }
            }
            taken[at]=false;
            not_taken.insert(i_take_me[at]);
            cout<<ans<<"\n";
        }
    }
    
}

Compilation message (stderr)

ballmachine.cpp: In function 'int find_min_in_subtree(int)':
ballmachine.cpp:4:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                            ^
ballmachine.cpp:19:5: note: in expansion of macro 'rep'
   19 |     rep(i,0,kids[node].size()){
      |     ^~~
ballmachine.cpp:4:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                                       ~~~~^~~~~
ballmachine.cpp:19:5: note: in expansion of macro 'rep'
   19 |     rep(i,0,kids[node].size()){
      |     ^~~
ballmachine.cpp: In function 'void order_dfs(int)':
ballmachine.cpp:4:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                            ^
ballmachine.cpp:38:9: note: in expansion of macro 'rep'
   38 |         rep(i,0,kids[node].size()){
      |         ^~~
ballmachine.cpp:4:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                                       ~~~~^~~~~
ballmachine.cpp:38:9: note: in expansion of macro 'rep'
   38 |         rep(i,0,kids[node].size()){
      |         ^~~
ballmachine.cpp: In function 'void build_up(int)':
ballmachine.cpp:4:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                            ^
ballmachine.cpp:52:5: note: in expansion of macro 'rep'
   52 |     rep(i,1,up[node].size()){
      |     ^~~
ballmachine.cpp:4:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                                       ~~~~^~~~~
ballmachine.cpp:52:5: note: in expansion of macro 'rep'
   52 |     rep(i,1,up[node].size()){
      |     ^~~
ballmachine.cpp:4:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                            ^
ballmachine.cpp:55:5: note: in expansion of macro 'rep'
   55 |     rep(i,0,kids[node].size()){
      |     ^~~
ballmachine.cpp:4:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                                       ~~~~^~~~~
ballmachine.cpp:55:5: note: in expansion of macro 'rep'
   55 |     rep(i,0,kids[node].size()){
      |     ^~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:4:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                            ^
ballmachine.cpp:66:5: note: in expansion of macro 'rep'
   66 |     rep(i,0,N){
      |     ^~~
ballmachine.cpp:4:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                            ^
ballmachine.cpp:98:5: note: in expansion of macro 'rep'
   98 |     rep(i,0,N){
      |     ^~~
ballmachine.cpp:4:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                            ^
ballmachine.cpp:101:13: note: in expansion of macro 'rep'
  101 |             rep(j,0,kids[i].size()){
      |             ^~~
ballmachine.cpp:4:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                                       ~~~~^~~~~
ballmachine.cpp:101:13: note: in expansion of macro 'rep'
  101 |             rep(j,0,kids[i].size()){
      |             ^~~
ballmachine.cpp:4:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                            ^
ballmachine.cpp:106:13: note: in expansion of macro 'rep'
  106 |             rep(j,0,v.size()){
      |             ^~~
ballmachine.cpp:4:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                                       ~~~~^~~~~
ballmachine.cpp:106:13: note: in expansion of macro 'rep'
  106 |             rep(j,0,v.size()){
      |             ^~~
ballmachine.cpp:4:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                            ^
ballmachine.cpp:122:5: note: in expansion of macro 'rep'
  122 |     rep(i,0,N){
      |     ^~~
ballmachine.cpp:4:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                            ^
ballmachine.cpp:141:5: note: in expansion of macro 'rep'
  141 |     rep(i,0,Q){
      |     ^~~
ballmachine.cpp:4:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define rep(i,a,b) for(int (i) = (a); (i) < (b); (i)++)
      |                            ^
ballmachine.cpp:144:13: note: in expansion of macro 'rep'
  144 |             rep(j,0,k){
      |             ^~~
ballmachine.cpp:170:42: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  170 |                     if(!taken[up[at][0]] || at==root) break;
      |                        ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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