Submission #283085

#	Time	Username	Problem	Language	Result	Execution time	Memory
283085		altalk	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	754 ms	30736 KiB

ballmachine

#include <bits/stdc++.h>
#define loop(a, b) for(int a = 0; a < b; ++a)
#define loop1(a, b) for(int a = 1; a <= b; ++a)
#define loopc(a, c, b) for(int a = c; a < b; ++a)
#define loopr(a, b) for(int a = b-1; a >= 0; --a)
#define mp make_pair

using namespace std;

typedef priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pair_queue;

int nn, qq, q, v;
vector<int> tree[100001];
int par[20][100001], sub[100001];
map<int, int> order;
pair_queue que;
bool val[100001];


void dfsdep(int n) {
    int s = n;
    loop(a, tree[n].size()) {
        dfsdep(tree[n][a]);
        s = min(s, sub[tree[n][a]]);
    }
    sub[n] = s;
}

bool ord(const int &a, const int &b) {
    return sub[a] < sub[b];
}

void dfsord(int n) {
    sort(tree[n].begin(), tree[n].end(), ord);
    loop(a, tree[n].size()) {
        dfsord(tree[n][a]);
    }
    order[n] = que.size();
    que.push(mp(order[n], n));
}

int main() {
    cin >> nn >> qq;
    loop1(a, nn) {
        cin >> par[0][a];
        tree[par[0][a]].push_back(a);
    }
    loop1(a, 18) {
        loop1(b, nn) {
            par[a][b] = par[a-1][par[a-1][b]];
        }
    }

    /*loop(a, 18) {
        loop1(b, nn) {
            cout << par[a][b] << " " ;
        }
        cout << endl;
    }*/
    dfsdep(0);
    dfsord(0);
    /*loop1(a, nn) {
        cout << sub[a] << " ";
    }
    cout << endl;*/
    pair<int, int> vv;
    int dd, pp;
    loop(w, qq) {
        cin >> q >> v;
        if (q==1) {
            while (v--) {
                vv = que.top();
                val[vv.second] = true;
                que.pop();
            }
            cout << vv.second << endl;
        }
        else if (q==2) {
            pp = v;
            dd = 0;
            loopr(a, 18) {
                //cout <<pp << " " << dd << " " << a << endl;
                //cout << par[a][pp] << endl << endl;;
                if (val[par[a][pp]]) {
                    pp = par[a][pp];
                    dd += 1<<a;
                }
            }
            val[pp] = false;
            que.push(mp(order[pp], pp));
            //cout <<pp << " " << dd << endl;
            cout << dd << endl;
        }
        /*loop1(a, nn) {
            cout << val[a] << " ";
        }
        cout << endl;*/
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfsdep(int)':
ballmachine.cpp:2:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define loop(a, b) for(int a = 0; a < b; ++a)
......
   22 |     loop(a, tree[n].size()) {
      |          ~~~~~~~~~~~~~~~~~           
ballmachine.cpp:22:5: note: in expansion of macro 'loop'
   22 |     loop(a, tree[n].size()) {
      |     ^~~~
ballmachine.cpp: In function 'void dfsord(int)':
ballmachine.cpp:2:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define loop(a, b) for(int a = 0; a < b; ++a)
......
   35 |     loop(a, tree[n].size()) {
      |          ~~~~~~~~~~~~~~~~~           
ballmachine.cpp:35:5: note: in expansion of macro 'loop'
   35 |     loop(a, tree[n].size()) {
      |     ^~~~

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