Submission #102352

#	Time	Username	Problem	Language	Result	Execution time	Memory
102352		TomGautot	Ball Machine (BOI13_ballmachine)	C++14	87.46 / 100	1078 ms	34548 KiB

ballmachine

#include <bits/stdc++.h>

#define INF 999999999

using namespace std;

vector<vector<int> > treeAdj;
vector<int> smallestInSubtree, freePlacesInSubtree, depth, reverseTree;
vector<int> fillOrderId, fillIdToNode;
vector<vector<int> > jumpTable;
vector<bool> available;
priority_queue<int, vector<int>, greater<int> > availableSpots;
int n, q;
int root;
int lastRolledDepth;

void computeData(int node, int d){

    int chld = treeAdj[node].size();
    depth[node] = d;
    //printf("Getting data for node %d (depth %d)\n", node, d);
    if(chld == 0){
        //printf("IT S A LEAF!\n");
        smallestInSubtree[node] = node;
        freePlacesInSubtree[node] = 1;
        return;
    }

    int sml = node;
    int fps = 1;
    int v;

    vector<pair<int, int> > newSortedAdj;

    for(int i = 0; i < chld; i++){
        v = treeAdj[node][i];
        //printf("%d -th child of %d is %d\n", i+1, node, v);
        computeData(v, d+1);
        newSortedAdj.push_back({smallestInSubtree[v], v});
        sml = min(sml, smallestInSubtree[v]);
        fps+= freePlacesInSubtree[v];
    }

    sort(newSortedAdj.begin(), newSortedAdj.end());
    for(int i = 0; i < chld; i++){
        treeAdj[node][i] = newSortedAdj[i].second;
    }

    smallestInSubtree[node] = sml;
    freePlacesInSubtree[node] = fps;

    //printf("Got data for node %d (depth %d)\n", node, d);
    return;
}

int computeFillOrderId(int node, int id){
    int sz = treeAdj[node].size();
    int v;
    for(int i = 0; i < sz; i++){
        v = treeAdj[node][i];
        id = computeFillOrderId(v, id);
    }

    fillOrderId[node] = id;
    fillIdToNode[id] = node;
    //printf("Node %d has fill order id %d\n", node, id);
    return id+1;
}

void computeJumpTable(int node){
    int mxj;
    if(node == root) mxj = 0;
    else mxj = log2(depth[node])+1;

    //printf("Can jump at most of %d from %d\n", mxj, node);

    for(int i = 0; i < mxj; i++){
        if(i == 0){
            jumpTable[node][0] = reverseTree[node];
        }
        else{
            jumpTable[node][i] = jumpTable[jumpTable[node][i-1]][i-1];
        }

        //printf("A jump of %d from %d lands at %d\n", 1<<i, node, jumpTable[node][i]);

    }

    int sz = treeAdj[node].size();
    for(int i = 0; i < sz; i++){
        computeJumpTable(treeAdj[node][i]);
    }

}

int jumpInTree(int node, int jumpVal){
    for(int i = 0; jumpVal != 0; jumpVal = jumpVal>>1){
        //printf("Round %d, jumpVal is %d\n", i, jumpVal);
        if(jumpVal&1){
          //  printf("Jumping of %d from %d\n", 1<<i, node);
            node = jumpTable[node][i];
        }
        i++;
    }
    return node;
}

void printTreeState(){
    printf("myIds: ");
    for(int i = 0; i < n; i++){
        printf("%d ", i);
    }

    printf("\nDepth: ");

    for(int i = 0; i < n; i++){
        printf("%d ", depth[i]);
    }

    printf("\nfree?: ");

    for(int i = 0; i < n; i++){
        printf("%d ", (available[i]?1:0));
    }
    printf("\n");
}

void addBallsWithPQ(int val){
    int spot;
    for(int i = 0; i < val; i++){
        spot = availableSpots.top();
        availableSpots.pop();
        available[fillIdToNode[spot]] = false;
    }
    cout << fillIdToNode[spot]+1 << endl;
}

void removeBallWithPQ(int node){
    int maxJump = depth[node];
    int minJump = 0;
    int md;
    int guess;

    while(minJump <= maxJump){
        md = (minJump + maxJump)/2;

        //printf("Trying to jump from %d of %d : ", node, md);

        guess = jumpInTree(node, md);

        //printf("landed on %d\n", guess);

        if(available[guess]){
            maxJump = md-1;
        }
        else{
            if(guess == root || available[reverseTree[guess]]){
                //printf("Highest ball above %d is %d\n", node, guess);
                available[guess] = true;
                lastRolledDepth = depth[guess];
                availableSpots.push(fillOrderId[guess]);
                return;
            }
            else{
                minJump = md+1;
            }
        }

    }

    return;


    /*int index = val;
    int last = index;

    while(true){
        if(available[index]){
            lastRolledDepth = depth[last];
            if(last != index) availableSpots.push(fillOrderId[last]);
            available[last] = true;
            return;
        }
        else if(index == root){
            lastRolledDepth = depth[root];
            if(last != index) availableSpots.push(fillOrderId[root]);
            available[root] = true;
            return;
        }
        last = index;
        index = reverseTree[index];
    }*/

}

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

    int p;
    cin >> n >> q;
    depth.resize(n);
    reverseTree.resize(n);
    treeAdj.resize(n);
    smallestInSubtree.resize(n);
    freePlacesInSubtree.resize(n);
    fillIdToNode.resize(n);
    fillOrderId.resize(n);
    jumpTable.resize(n);
    available.assign(n, true);
    int maxBinaryJump = log2(n)+1;
    for(int i = 0; i < n; i++){
        jumpTable[i].resize(maxBinaryJump);
        cin >> p;
        if(p == 0) root = i;
        else{
            treeAdj[p-1].push_back(i);
            reverseTree[i] = p-1;
        }
    }

    //cout << "Going to compute data" << endl;

    //return 0;

    computeData(root, 0);
    computeFillOrderId(root, 0);
    computeJumpTable(root);

    for(int i = 0; i < n; i++){
        availableSpots.push(i);
    }

    /*
    printf("Priority queue content: ");
    for(int i = 0; i < n; i++){
        printf("%d ", availableSpots.top());
        availableSpots.pop();
    }
    printf("\n");

    for(int i = 0; i < n; i++){
        availableSpots.push(i);
    }
    */

    //return 0;
    //cout << "Data was computedd successfully" << endl;

    int action, val;
    for(int i = 0; i < q; i++){
        cin >> action >> val;


        if(action == 1){
            addBallsWithPQ(val);
        }
        else{
            val--;
            removeBallWithPQ(val);
            //cout << "Last rolled depth is " << *lastRolledDepth << endl;
            cout << depth[val] - lastRolledDepth << endl;
        }

        //printTreeState();

    }


    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void addBallsWithPQ(int)':
ballmachine.cpp:129:9: warning: 'spot' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int spot;
         ^~~~

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 28.571428571428573 / 40
• Subtask 4: 3.888888888888889 / 5