oj.uz

Submission #643526

# Submission time Handle Problem Language Result Execution time Memory
643526 2022-09-22T09:35:31 Z KindaNameless Ball Machine (BOI13_ballmachine) C++14
100 / 100
 173 ms 22680 KB 
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<numeric>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;

#define ll long long
#define ld long double

vector<int> adj[100005];
bool occupied[100005];
int mn[100005], order[100005], par[100005][17];
int timer = 0;

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

void dfs(int cur){
    for(int j = 1; j < 17; ++j){
        par[cur][j] = par[par[cur][j-1]][j-1];
    }
    mn[cur] = cur;
    for(int ch : adj[cur]){
        par[ch][0] = cur;
        dfs(ch);
        mn[cur] = min(mn[cur], mn[ch]);
    }
}

void det(int cur){
    sort(adj[cur].begin(), adj[cur].end(), cmp);
    for(int ch : adj[cur]){
        det(ch);
    }
    order[cur] = ++timer;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N, Q; cin >> N >> Q;

    int root = 0;
    for(int i = 1; i <= N; ++i){
        int p; cin >> p;
        if(p == 0)root = i;
        else adj[p].push_back(i);
    }

    dfs(root);
    det(root);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(int i = 1; i <= N; ++i){
        pq.push(make_pair(order[i], i));
    }

    for(int i = 1; i <= Q; ++i){
        int op; cin >> op;
        if(op == 1){
            int k; cin >> k;
            while(k--){
                if(k == 0)cout << pq.top().second << "\n";
                occupied[pq.top().second] = 1;
                pq.pop();
            }
        }
        else{
            int x, diff = 0; cin >> x;
            for(int j = 16; j >= 0; --j){
                if(occupied[par[x][j]]){
                    x = par[x][j];
                    diff += (1 << j);
                }
            }
            occupied[x] = 0;
            pq.push(make_pair(order[x], x));
            cout << diff << "\n";
        }
    }

    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 69 ms 9700 KB Output is correct
3 Correct 52 ms 9784 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2684 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 5 ms 3156 KB Output is correct
10 Correct 15 ms 4568 KB Output is correct
11 Correct 70 ms 9712 KB Output is correct
12 Correct 59 ms 9764 KB Output is correct
13 Correct 71 ms 9724 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6728 KB Output is correct
2 Correct 121 ms 17368 KB Output is correct
3 Correct 71 ms 12752 KB Output is correct
4 Correct 42 ms 7432 KB Output is correct
5 Correct 42 ms 7240 KB Output is correct
6 Correct 39 ms 7240 KB Output is correct
7 Correct 41 ms 6416 KB Output is correct
8 Correct 28 ms 6608 KB Output is correct
9 Correct 109 ms 17712 KB Output is correct
10 Correct 105 ms 17244 KB Output is correct
11 Correct 94 ms 17184 KB Output is correct
12 Correct 107 ms 14976 KB Output is correct
13 Correct 84 ms 20160 KB Output is correct
14 Correct 74 ms 12756 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 10356 KB Output is correct
2 Correct 123 ms 15468 KB Output is correct
3 Correct 95 ms 18744 KB Output is correct
4 Correct 90 ms 14760 KB Output is correct
5 Correct 78 ms 14536 KB Output is correct
6 Correct 80 ms 14456 KB Output is correct
7 Correct 79 ms 12892 KB Output is correct
8 Correct 93 ms 18656 KB Output is correct
9 Correct 112 ms 17872 KB Output is correct
10 Correct 122 ms 17348 KB Output is correct
11 Correct 115 ms 17480 KB Output is correct
12 Correct 124 ms 15484 KB Output is correct
13 Correct 173 ms 22680 KB Output is correct
14 Correct 83 ms 12868 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 17896 KB Output is correct
2 Correct 128 ms 15440 KB Output is correct
3 Correct 94 ms 22460 KB Output is correct
4 Correct 125 ms 17972 KB Output is correct
5 Correct 148 ms 17408 KB Output is correct
6 Correct 102 ms 17348 KB Output is correct
7 Correct 111 ms 15416 KB Output is correct
8 Correct 120 ms 22460 KB Output is correct
9 Correct 63 ms 12856 KB Output is correct