oj.uz

Submission #547784

# Submission time Handle Problem Language Result Execution time Memory
547784 2022-04-11T18:16:50 Z _martynas Ball Machine (BOI13_ballmachine) C++11
100 / 100
 170 ms 25268 KB 
#include <bits/stdc++.h>

using namespace std;

#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(), (a).end()

using pii = pair<int, int>;

const int MXN = 1e5+5;
const int MXK = 18;

int n, q;
int P[MXN], H[MXN];
int BL[MXK][MXN];
priority_queue<pii, vector<pii>, greater<pii>> PQ;
vector<int> Adj[MXN];
pii node[MXN];
int mn[MXN];
bool taken[MXN];
int root = -1;
int priority = 0;

void dfsmn(int u)
{
    mn[u] = u;
    for(int v : Adj[u]) {
        dfsmn(v);
        mn[u] = min(mn[u], mn[v]);
    }
}

void dfs(int u, int h)
{
    sort(all(Adj[u]),
    [&](int i, int j)
    {
        return mn[i] < mn[j];
    });
    for(int v : Adj[u]) {
        dfs(v, h+1);
    }
    node[u] = {priority++, u};
    H[u] = h;
    PQ.push(node[u]);
}

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

    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        int p; cin >> p;
        if(p) {
            P[i] = p;
            Adj[p].PB(i);
        }
        else {
            root = i;
            P[i] = i;
        }
    }

    fill(mn, mn+n+1, 2*n);
    dfsmn(root);
    dfs(root, 0);
    for(int k = 0; k < MXK; k++)
    for(int i = 1; i <= n; i++) {
        if(k) {
            BL[k][i] = BL[k-1][BL[k-1][i]];
        }
        else {
            BL[k][i] = P[i];
        }
    }

//    auto pqcopy = PQ;
//    while(!pqcopy.empty()) {
//        cerr << pqcopy.top().S << " ";
//        pqcopy.pop();
//    }
//    cerr << "\n";

    for(int qq = 0; qq < q; qq++) {
        int t, x;
        cin >> t >> x;
        if(t == 1) {
            // add
            int last = -1;
            for(int i = 0; i < x; i++) {
                auto u = PQ.top().S;
                PQ.pop();
                taken[u] = true;
                last = u;
            }
            cout << last << "\n";
        }
        else {
            // remove
            int up = 0;
            for(int k = MXK-1; k >= 0; k--) {
                while(taken[BL[k][x]] && x != root) {

                    up += H[x]-H[BL[k][x]];
                    x = BL[k][x];
                }
            }
            taken[x] = false;
            PQ.push(node[x]);
            cout << up << "\n";
        }
    }

    return 0;
}
/*
8 4
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8
*/

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 67 ms 11700 KB Output is correct
3 Correct 41 ms 11644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2900 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 6 ms 3284 KB Output is correct
10 Correct 13 ms 5004 KB Output is correct
11 Correct 63 ms 11680 KB Output is correct
12 Correct 42 ms 11612 KB Output is correct
13 Correct 66 ms 11716 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7280 KB Output is correct
2 Correct 94 ms 19884 KB Output is correct
3 Correct 52 ms 14624 KB Output is correct
4 Correct 36 ms 8572 KB Output is correct
5 Correct 42 ms 8464 KB Output is correct
6 Correct 41 ms 8508 KB Output is correct
7 Correct 43 ms 7500 KB Output is correct
8 Correct 27 ms 7284 KB Output is correct
9 Correct 96 ms 20248 KB Output is correct
10 Correct 111 ms 19976 KB Output is correct
11 Correct 89 ms 19788 KB Output is correct
12 Correct 91 ms 17640 KB Output is correct
13 Correct 82 ms 22552 KB Output is correct
14 Correct 62 ms 14604 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 11724 KB Output is correct
2 Correct 98 ms 18088 KB Output is correct
3 Correct 103 ms 20708 KB Output is correct
4 Correct 88 ms 16856 KB Output is correct
5 Correct 75 ms 16452 KB Output is correct
6 Correct 65 ms 16444 KB Output is correct
7 Correct 66 ms 14948 KB Output is correct
8 Correct 91 ms 20716 KB Output is correct
9 Correct 114 ms 20416 KB Output is correct
10 Correct 134 ms 20068 KB Output is correct
11 Correct 113 ms 19952 KB Output is correct
12 Correct 138 ms 17992 KB Output is correct
13 Correct 170 ms 25268 KB Output is correct
14 Correct 75 ms 14732 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 20576 KB Output is correct
2 Correct 145 ms 18048 KB Output is correct
3 Correct 72 ms 24256 KB Output is correct
4 Correct 118 ms 20604 KB Output is correct
5 Correct 128 ms 20164 KB Output is correct
6 Correct 98 ms 19920 KB Output is correct
7 Correct 105 ms 18008 KB Output is correct
8 Correct 91 ms 24248 KB Output is correct
9 Correct 60 ms 14664 KB Output is correct