oj.uz

Submission #102352

# Submission time Handle Problem Language Result Execution time Memory
102352 2019-03-24T13:16:59 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
87.4603 / 100
 1000 ms 34548 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 372 ms 12888 KB Output is correct
3 Correct 272 ms 13044 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 23 ms 1024 KB Output is correct
10 Correct 61 ms 3356 KB Output is correct
11 Correct 350 ms 13024 KB Output is correct
12 Correct 286 ms 12964 KB Output is correct
13 Correct 275 ms 12992 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 7160 KB Output is correct
2 Correct 644 ms 26388 KB Output is correct
3 Correct 285 ms 18676 KB Output is correct
4 Correct 254 ms 8972 KB Output is correct
5 Correct 286 ms 8624 KB Output is correct
6 Correct 259 ms 8692 KB Output is correct
7 Correct 283 ms 7164 KB Output is correct
8 Correct 167 ms 7288 KB Output is correct
9 Correct 505 ms 27040 KB Output is correct
10 Correct 717 ms 26392 KB Output is correct
11 Correct 583 ms 26288 KB Output is correct
12 Correct 558 ms 22292 KB Output is correct
13 Correct 430 ms 30720 KB Output is correct
14 Correct 274 ms 18664 KB Output is correct

Subtask #3
28.5714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 13728 KB Output is correct
2 Execution timed out 1077 ms 23056 KB Time limit exceeded
3 Correct 868 ms 27760 KB Output is correct
4 Correct 565 ms 21620 KB Output is correct
5 Correct 634 ms 21036 KB Output is correct
6 Correct 722 ms 21268 KB Output is correct
7 Correct 567 ms 18324 KB Output is correct
8 Correct 823 ms 27888 KB Output is correct
9 Correct 880 ms 26968 KB Output is correct
10 Correct 983 ms 26540 KB Output is correct
11 Execution timed out 1073 ms 26548 KB Time limit exceeded
12 Execution timed out 1016 ms 23068 KB Time limit exceeded
13 Execution timed out 1078 ms 34548 KB Time limit exceeded
14 Correct 346 ms 19044 KB Output is correct

Subtask #4
3.88888888889 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 984 ms 27084 KB Output is correct
2 Correct 842 ms 23056 KB Output is correct
3 Correct 449 ms 34544 KB Output is correct
4 Execution timed out 1032 ms 27116 KB Time limit exceeded
5 Correct 984 ms 26548 KB Output is correct
6 Correct 553 ms 26416 KB Output is correct
7 Execution timed out 1016 ms 23020 KB Time limit exceeded
8 Correct 486 ms 34540 KB Output is correct
9 Correct 272 ms 18788 KB Output is correct