Submission #467877

#	Time	Username	Problem	Language	Result	Execution time	Memory
467877		JasperL	Ball Machine (BOI13_ballmachine)	C++14	16.11 / 100	384 ms	21952 KiB

ballmachine

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define maxn 100005
#define maxh 20

int n, q, rt;
vector<int> e[maxn];
int jump[maxn][maxh];
vector<int> pos;
int idx[maxn];
priority_queue<pair<int,int>> pq;

bool ball[maxn];

void dfs(int i) {
    for (int j : e[i]) dfs(j);
    pos.push_back(i);
}

void add() {
    auto z = pq.top(); pq.pop();
    int i = z.second;
    ball[i] = true;
    //cout << i + 1 << endl;
}

int rem(int i) {
    int z = 0;
    for (int j = maxh-1; j >= 0; j--) {
        if (jump[i][j] == -1 || ball[jump[i][j]] == false) continue;
        z += (1<<j); i = jump[i][j];
    }
    ball[i] = false;
    pq.push({-idx[i],i});
    return z;
}

int main() {
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> jump[i][0]; jump[i][0]--;
        if (jump[i][0] != -1) e[jump[i][0]].push_back(i);
        else rt = i;
    }
    for (int i = 0; i < n; i++) sort(e[i].begin(),e[i].end());
    for (int j = 1; j < maxh; j++) {
        for (int i = 0; i < n; i++) {
            if (jump[i][j-1] == -1) jump[i][j] = -1;
            else jump[i][j] = jump[jump[i][j-1]][j-1];
        }
    }
    dfs(rt);
    //for (int j : pos) cout << j+1 << " ";
    //cout << endl;
    for (int i = 0; i < n; i++) idx[pos[i]] = i;
    for (int i = 0; i < n; i++) {
        pq.push({-idx[i],i});
    }
    for (int i = 0; i < q; i++) {
        int t; cin >> t;
        if (t == 1) {
            int sz; cin >> sz;
            for (int j = 0; j < sz-1; j++) add();
            int j = pq.top().second;
            cout << j + 1 << endl;
            add();
        } else {
            int j; cin >> j; j--;
            int res = rem(j);
            cout << res << endl;
        }
    }
}

• Subtask 1: 0 / 25
• Subtask 2: 6.428571428571429 / 30
• Subtask 3: 8.571428571428571 / 40
• Subtask 4: 1.1111111111111112 / 5