답안 #763602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
763602	2023-06-22T13:47:30 Z	Ellinor	Ball Machine (BOI13_ballmachine)	C++14	48.0525 / 100	1000 ms	28448 KB

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

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.84615384615 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	340 KB	Output isn't correct
2	Incorrect	237 ms	15084 KB	Output isn't correct
3	Correct	186 ms	15020 KB	Output is correct
4	Execution timed out	1079 ms	212 KB	Time limit exceeded
5	Incorrect	1 ms	340 KB	Output isn't correct
6	Incorrect	2 ms	468 KB	Output isn't correct
7	Execution timed out	1079 ms	468 KB	Time limit exceeded
8	Execution timed out	1082 ms	468 KB	Time limit exceeded
9	Execution timed out	1085 ms	1108 KB	Time limit exceeded
10	Execution timed out	1075 ms	3492 KB	Time limit exceeded
11	Incorrect	238 ms	14968 KB	Output isn't correct
12	Correct	189 ms	14896 KB	Output is correct
13	Execution timed out	1077 ms	14280 KB	Time limit exceeded

Subtask #2

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	124 ms	5896 KB	Output is correct
2	Correct	291 ms	24840 KB	Output is correct
3	Correct	210 ms	21564 KB	Output is correct
4	Correct	149 ms	8268 KB	Output is correct
5	Correct	167 ms	8144 KB	Output is correct
6	Correct	144 ms	8012 KB	Output is correct
7	Correct	153 ms	7248 KB	Output is correct
8	Correct	121 ms	5952 KB	Output is correct
9	Correct	279 ms	25436 KB	Output is correct
10	Correct	276 ms	24884 KB	Output is correct
11	Correct	263 ms	24900 KB	Output is correct
12	Correct	264 ms	23252 KB	Output is correct
13	Correct	292 ms	25272 KB	Output is correct
14	Correct	214 ms	21548 KB	Output is correct

Subtask #3

11.4285714286 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1086 ms	12472 KB	Time limit exceeded
2	Execution timed out	1076 ms	22916 KB	Time limit exceeded
3	Correct	292 ms	22860 KB	Output is correct
4	Execution timed out	1087 ms	19720 KB	Time limit exceeded
5	Correct	203 ms	19812 KB	Output is correct
6	Correct	187 ms	19804 KB	Output is correct
7	Incorrect	212 ms	18980 KB	Output isn't correct
8	Correct	222 ms	22808 KB	Output is correct
9	Execution timed out	1072 ms	24568 KB	Time limit exceeded
10	Execution timed out	1089 ms	24116 KB	Time limit exceeded
11	Incorrect	302 ms	25024 KB	Output isn't correct
12	Execution timed out	1082 ms	22980 KB	Time limit exceeded
13	Execution timed out	1062 ms	27596 KB	Time limit exceeded
14	Incorrect	260 ms	22040 KB	Output isn't correct

Subtask #4

2.77777777778 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	334 ms	25524 KB	Output isn't correct
2	Incorrect	317 ms	23852 KB	Output isn't correct
3	Correct	241 ms	28448 KB	Output is correct
4	Incorrect	299 ms	25548 KB	Output isn't correct
5	Correct	321 ms	25036 KB	Output is correct
6	Correct	302 ms	25084 KB	Output is correct
7	Incorrect	304 ms	23900 KB	Output isn't correct
8	Correct	255 ms	28412 KB	Output is correct
9	Correct	209 ms	21624 KB	Output is correct