oj.uz

Submission #283052

# Submission time Handle Problem Language Result Execution time Memory
283052 2020-08-25T09:19:55 Z altalk Ball Machine (BOI13_ballmachine) C++14
21.8254 / 100
 748 ms 29368 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;
            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

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 536 ms 12968 KB Output isn't correct
3 Incorrect 408 ms 13268 KB Output isn't correct
4 Incorrect 2 ms 2816 KB Output isn't correct
5 Incorrect 3 ms 2944 KB Output isn't correct
6 Incorrect 5 ms 2944 KB Output isn't correct
7 Incorrect 7 ms 2944 KB Output isn't correct
8 Incorrect 7 ms 2944 KB Output isn't correct
9 Incorrect 35 ms 3456 KB Output isn't correct
10 Incorrect 98 ms 5496 KB Output isn't correct
11 Incorrect 533 ms 12912 KB Output isn't correct
12 Incorrect 409 ms 13168 KB Output isn't correct
13 Incorrect 525 ms 12908 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 8128 KB Output is correct
2 Incorrect 637 ms 23148 KB Output isn't correct
3 Incorrect 426 ms 18028 KB Output isn't correct
4 Incorrect 356 ms 9332 KB Output isn't correct
5 Incorrect 352 ms 9204 KB Output isn't correct
6 Incorrect 349 ms 9216 KB Output isn't correct
7 Incorrect 351 ms 8052 KB Output isn't correct
8 Correct 273 ms 8052 KB Output is correct
9 Incorrect 609 ms 23784 KB Output isn't correct
10 Incorrect 629 ms 23156 KB Output isn't correct
11 Incorrect 669 ms 23148 KB Output isn't correct
12 Incorrect 634 ms 20456 KB Output isn't correct
13 Correct 473 ms 26216 KB Output is correct
14 Incorrect 457 ms 18240 KB Output isn't correct

Subtask #3
14.2857142857 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 13424 KB Output is correct
2 Incorrect 672 ms 21100 KB Output isn't correct
3 Correct 431 ms 24104 KB Output is correct
4 Incorrect 412 ms 19560 KB Output isn't correct
5 Incorrect 407 ms 19176 KB Output isn't correct
6 Incorrect 414 ms 19308 KB Output isn't correct
7 Incorrect 398 ms 17260 KB Output isn't correct
8 Correct 447 ms 24040 KB Output is correct
9 Incorrect 650 ms 23788 KB Output isn't correct
10 Incorrect 650 ms 23404 KB Output isn't correct
11 Incorrect 707 ms 23276 KB Output isn't correct
12 Incorrect 694 ms 20972 KB Output isn't correct
13 Correct 748 ms 29368 KB Output is correct
14 Correct 609 ms 17772 KB Output is correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 678 ms 23732 KB Output isn't correct
2 Incorrect 650 ms 20968 KB Output isn't correct
3 Correct 527 ms 29164 KB Output is correct
4 Incorrect 643 ms 23660 KB Output isn't correct
5 Incorrect 641 ms 23220 KB Output isn't correct
6 Incorrect 612 ms 23300 KB Output isn't correct
7 Incorrect 681 ms 20900 KB Output isn't correct
8 Correct 502 ms 29252 KB Output is correct
9 Incorrect 445 ms 17960 KB Output isn't correct