oj.uz

Submission #666880

# Submission time Handle Problem Language Result Execution time Memory
666880 2022-11-29T20:14:19 Z definitelynotmee Ball Machine (BOI13_ballmachine) C++
100 / 100
 138 ms 20928 KB 
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

struct lift{
    int pai, d, jmp;
};


int main(){
    cin.tie(0)->sync_with_stdio(0);

    int n, q;
    cin >> n >> q;

    vector<int> pai(n+1);
    int root = 0;

    matrix<int> g(n+1);

    for(int i = 1; i <= n; i++){
        cin >> pai[i];
        if(pai[i]!=0){
            g[pai[i]].push_back(i);
        } else root = i;
    }

    vector<int> mn(n+1,1e9);
    auto prec=[&](int id, auto dfs)->void{
        mn[id] = id;
        for(int i : g[id]){
            dfs(i,dfs);
            mn[id] = min(mn[id],mn[i]);
        }
        sort(all(g[id]),[&](int a, int b){
            return mn[a] < mn[b];
        });
    };
    prec(root,prec);

    priority_queue<pii,vector<pii>,greater<pii>> pq;

    int timer = -1;

    vector<int> order(n+1), taken(n+1);

    vector<lift> trick(n+1);
    trick[root] = {root,0,root};

    auto append =[&](int f){
        trick[f].pai = pai[f];
        trick[f].d = 1;
        trick[f].jmp = pai[f];
        while(trick[trick[f].jmp].d == trick[f].d){
            trick[f].d*=2;
            trick[f].jmp = trick[trick[f].jmp].jmp;
        }
    };

    auto dfs=[&](int id, auto dfs)->void{
        for(int i : g[id]){
            append(i);
            dfs(i,dfs);
        }
        order[id] = ++timer;
        pq.push({order[id],id});
    };
    dfs(root,dfs);

    while(q--){
        int type, x;
        cin >> type >> x;
        if(type == 1){
            int cur;
            while(x--){
                cur = pq.top().ss;
                taken[cur] = 1;
                pq.pop();
            }
            cout << cur << '\n';
        } else {
            int ct = 0;
            while(taken[pai[x]]){
                if(taken[trick[x].jmp])
                    ct+=trick[x].d, x = trick[x].jmp;
                else ct++, x = trick[x].pai;
            }
            pq.push({order[x],x});
            taken[x] = 0;
            cout  << ct << '\n';
        }
    }

}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:87:28: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |             cout << cur << '\n';
      |                            ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 57 ms 5656 KB Output is correct
3 Correct 40 ms 5732 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 12 ms 1620 KB Output is correct
11 Correct 56 ms 5544 KB Output is correct
12 Correct 41 ms 5696 KB Output is correct
13 Correct 59 ms 5516 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4304 KB Output is correct
2 Correct 75 ms 13940 KB Output is correct
3 Correct 52 ms 8016 KB Output is correct
4 Correct 33 ms 4656 KB Output is correct
5 Correct 33 ms 4560 KB Output is correct
6 Correct 36 ms 4484 KB Output is correct
7 Correct 34 ms 3444 KB Output is correct
8 Correct 24 ms 4364 KB Output is correct
9 Correct 84 ms 14400 KB Output is correct
10 Correct 79 ms 13880 KB Output is correct
11 Correct 74 ms 13984 KB Output is correct
12 Correct 71 ms 10980 KB Output is correct
13 Correct 71 ms 18476 KB Output is correct
14 Correct 50 ms 7996 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7452 KB Output is correct
2 Correct 102 ms 11400 KB Output is correct
3 Correct 80 ms 16716 KB Output is correct
4 Correct 64 ms 11784 KB Output is correct
5 Correct 59 ms 11460 KB Output is correct
6 Correct 59 ms 11480 KB Output is correct
7 Correct 64 ms 9272 KB Output is correct
8 Correct 82 ms 16724 KB Output is correct
9 Correct 106 ms 14528 KB Output is correct
10 Correct 101 ms 14084 KB Output is correct
11 Correct 99 ms 14016 KB Output is correct
12 Correct 89 ms 11332 KB Output is correct
13 Correct 138 ms 20928 KB Output is correct
14 Correct 58 ms 8012 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 14556 KB Output is correct
2 Correct 92 ms 11384 KB Output is correct
3 Correct 77 ms 20728 KB Output is correct
4 Correct 113 ms 14588 KB Output is correct
5 Correct 92 ms 14108 KB Output is correct
6 Correct 94 ms 14032 KB Output is correct
7 Correct 94 ms 11312 KB Output is correct
8 Correct 84 ms 20768 KB Output is correct
9 Correct 50 ms 8012 KB Output is correct