oj.uz

Submission #283048

# Submission time Handle Problem Language Result Execution time Memory
283048 2020-08-25T09:17:40 Z altalk Ball Machine (BOI13_ballmachine) C++14
14.2857 / 100
 613 ms 30568 KB 
#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, 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 << order[a] << endl;
    }*/
    //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;
            //cout <<pp << " " << dd << endl;
            cout << dd << endl;
        }
        /*loop1(a, nn) {
            cout << val[a] << " ";
        }
        cout << endl;*/
    }
    return 0;
}

Compilation message

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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2816 KB Output isn't correct
2 Incorrect 450 ms 14060 KB Output isn't correct
3 Incorrect 406 ms 14120 KB Output isn't correct
4 Incorrect 2 ms 2816 KB Output isn't correct
5 Incorrect 3 ms 2816 KB Output isn't correct
6 Incorrect 5 ms 2944 KB Output isn't correct
7 Incorrect 6 ms 2944 KB Output isn't correct
8 Incorrect 7 ms 2944 KB Output isn't correct
9 Incorrect 32 ms 3456 KB Output isn't correct
10 Incorrect 85 ms 5504 KB Output isn't correct
11 Incorrect 438 ms 14064 KB Output isn't correct
12 Incorrect 408 ms 13988 KB Output isn't correct
13 Incorrect 461 ms 14064 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 265 ms 8436 KB Output isn't correct
2 Incorrect 571 ms 24664 KB Output isn't correct
3 Incorrect 426 ms 18796 KB Output isn't correct
4 Incorrect 308 ms 9984 KB Output isn't correct
5 Incorrect 306 ms 9716 KB Output isn't correct
6 Incorrect 305 ms 9764 KB Output isn't correct
7 Incorrect 303 ms 8608 KB Output isn't correct
8 Incorrect 266 ms 8436 KB Output isn't correct
9 Incorrect 533 ms 24940 KB Output isn't correct
10 Incorrect 554 ms 24552 KB Output isn't correct
11 Incorrect 553 ms 24428 KB Output isn't correct
12 Incorrect 546 ms 21744 KB Output isn't correct
13 Incorrect 506 ms 27240 KB Output isn't correct
14 Incorrect 434 ms 18796 KB Output isn't correct

Subtask #3
14.2857142857 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 13808 KB Output is correct
2 Incorrect 563 ms 22140 KB Output isn't correct
3 Correct 380 ms 24808 KB Output is correct
4 Incorrect 356 ms 20332 KB Output isn't correct
5 Incorrect 360 ms 19944 KB Output isn't correct
6 Incorrect 352 ms 20028 KB Output isn't correct
7 Incorrect 354 ms 18236 KB Output isn't correct
8 Correct 377 ms 24808 KB Output is correct
9 Incorrect 551 ms 24936 KB Output isn't correct
10 Incorrect 557 ms 24584 KB Output isn't correct
11 Incorrect 565 ms 24496 KB Output isn't correct
12 Incorrect 565 ms 22380 KB Output isn't correct
13 Correct 613 ms 30568 KB Output is correct
14 Correct 492 ms 19052 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 566 ms 24872 KB Output isn't correct
2 Incorrect 556 ms 22124 KB Output isn't correct
3 Incorrect 497 ms 30184 KB Output isn't correct
4 Incorrect 546 ms 24940 KB Output isn't correct
5 Incorrect 557 ms 24556 KB Output isn't correct
6 Incorrect 533 ms 24376 KB Output isn't correct
7 Incorrect 565 ms 22120 KB Output isn't correct
8 Incorrect 504 ms 30184 KB Output isn't correct
9 Incorrect 426 ms 18796 KB Output isn't correct