oj.uz

답안 #283085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
283085 2020-08-25T09:44:37 Z altalk Ball Machine (BOI13_ballmachine) C++14
100 / 100
 754 ms 30736 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, 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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 529 ms 14064 KB Output is correct
3 Correct 406 ms 14004 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 3 ms 2944 KB Output is correct
6 Correct 5 ms 2944 KB Output is correct
7 Correct 6 ms 2944 KB Output is correct
8 Correct 7 ms 2944 KB Output is correct
9 Correct 33 ms 3456 KB Output is correct
10 Correct 96 ms 5564 KB Output is correct
11 Correct 529 ms 14192 KB Output is correct
12 Correct 414 ms 13936 KB Output is correct
13 Correct 512 ms 13936 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 8308 KB Output is correct
2 Correct 733 ms 24312 KB Output is correct
3 Correct 452 ms 18540 KB Output is correct
4 Correct 379 ms 9880 KB Output is correct
5 Correct 387 ms 9976 KB Output is correct
6 Correct 377 ms 9716 KB Output is correct
7 Correct 360 ms 8696 KB Output is correct
8 Correct 273 ms 8308 KB Output is correct
9 Correct 617 ms 24972 KB Output is correct
10 Correct 624 ms 24428 KB Output is correct
11 Correct 592 ms 24424 KB Output is correct
12 Correct 610 ms 21736 KB Output is correct
13 Correct 471 ms 27256 KB Output is correct
14 Correct 430 ms 18540 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 294 ms 14064 KB Output is correct
2 Correct 672 ms 22124 KB Output is correct
3 Correct 442 ms 24812 KB Output is correct
4 Correct 445 ms 20500 KB Output is correct
5 Correct 398 ms 20076 KB Output is correct
6 Correct 442 ms 20160 KB Output is correct
7 Correct 418 ms 18152 KB Output is correct
8 Correct 437 ms 24808 KB Output is correct
9 Correct 658 ms 24844 KB Output is correct
10 Correct 668 ms 24416 KB Output is correct
11 Correct 657 ms 24424 KB Output is correct
12 Correct 647 ms 22124 KB Output is correct
13 Correct 754 ms 30736 KB Output is correct
14 Correct 586 ms 19052 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 665 ms 25196 KB Output is correct
2 Correct 643 ms 22248 KB Output is correct
3 Correct 479 ms 30188 KB Output is correct
4 Correct 683 ms 24960 KB Output is correct
5 Correct 643 ms 24528 KB Output is correct
6 Correct 631 ms 24556 KB Output is correct
7 Correct 705 ms 22248 KB Output is correct
8 Correct 492 ms 30188 KB Output is correct
9 Correct 468 ms 18540 KB Output is correct