oj.uz

Submission #102372

# Submission time Handle Problem Language Result Execution time Memory
102372 2019-03-24T14:33:40 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
16.2698 / 100
 605 ms 31632 KB 
#include <bits/stdc++.h>

#define INF 999999999
#define MAXN 100100

using namespace std;

vector<vector<int> > treeAdj;
int smallestInSubtree[MAXN], depth[MAXN], reverseTree[MAXN], fillOrderId[MAXN], fillIdToNode[MAXN];
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;
        return;
    }

    int sml = node;
    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]);
    }

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

    smallestInSubtree[node] = sml;

    //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){

    if(!available[root]){
        lastRolledDepth = depth[root];
        available[root] = true;
        availableSpots.push(root);
        return;
    }

    int maxJump = depth[node];
    int p;

    for(int i = 0;; i++){
        if((1LL << i) > maxJump){
            p = i-1;
            //printf("Stopped at i = %d cause would jump %d\n", i, (1<<i));
            break;
        }
    }

    //printf("Can jump at most %d\n", p);

    for(int i = p; i >= 0; i--){
      //      printf("Checking %d as potential jump land from %d\n", jumpTable[node][i]);
        if(!available[jumpTable[node][i]]){
            node = jumpTable[node][i];
        }
    }

    //printf("Found higher best stop to be %d\n",node);

    lastRolledDepth = depth[node];
    available[node] = true;
    availableSpots.push(node);

    return;
}

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

    int p;
    cin >> n >> q;
    treeAdj.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;
        }
    }

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

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

    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:125:9: warning: 'spot' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int spot;
         ^~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Incorrect 287 ms 11636 KB Output isn't correct
3 Incorrect 256 ms 11636 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 3 ms 384 KB Output isn't correct
6 Incorrect 4 ms 512 KB Output isn't correct
7 Incorrect 4 ms 512 KB Output isn't correct
8 Incorrect 5 ms 512 KB Output isn't correct
9 Incorrect 18 ms 1024 KB Output isn't correct
10 Incorrect 46 ms 2936 KB Output isn't correct
11 Incorrect 298 ms 11456 KB Output isn't correct
12 Incorrect 250 ms 11816 KB Output isn't correct
13 Incorrect 302 ms 11544 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 182 ms 6412 KB Output isn't correct
2 Incorrect 487 ms 23988 KB Output isn't correct
3 Correct 242 ms 17388 KB Output is correct
4 Incorrect 192 ms 7672 KB Output isn't correct
5 Incorrect 196 ms 7668 KB Output isn't correct
6 Incorrect 235 ms 7668 KB Output isn't correct
7 Incorrect 206 ms 6280 KB Output isn't correct
8 Incorrect 196 ms 6364 KB Output isn't correct
9 Incorrect 436 ms 24308 KB Output isn't correct
10 Incorrect 452 ms 23832 KB Output isn't correct
11 Incorrect 482 ms 24064 KB Output isn't correct
12 Incorrect 451 ms 20500 KB Output isn't correct
13 Incorrect 376 ms 28020 KB Output isn't correct
14 Correct 281 ms 17296 KB Output is correct

Subtask #3
11.4285714286 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 12484 KB Output isn't correct
2 Incorrect 568 ms 20872 KB Output isn't correct
3 Correct 401 ms 25316 KB Output is correct
4 Incorrect 315 ms 19576 KB Output isn't correct
5 Correct 318 ms 19344 KB Output is correct
6 Correct 334 ms 19220 KB Output is correct
7 Incorrect 309 ms 16828 KB Output isn't correct
8 Correct 330 ms 25328 KB Output is correct
9 Incorrect 428 ms 24564 KB Output isn't correct
10 Incorrect 444 ms 24108 KB Output isn't correct
11 Incorrect 522 ms 23988 KB Output isn't correct
12 Incorrect 483 ms 20884 KB Output isn't correct
13 Incorrect 605 ms 31632 KB Output isn't correct
14 Incorrect 317 ms 17384 KB Output isn't correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 540 ms 24528 KB Output isn't correct
2 Incorrect 517 ms 20880 KB Output isn't correct
3 Incorrect 437 ms 31472 KB Output isn't correct
4 Incorrect 541 ms 24520 KB Output isn't correct
5 Incorrect 488 ms 24012 KB Output isn't correct
6 Incorrect 414 ms 23940 KB Output isn't correct
7 Incorrect 477 ms 20812 KB Output isn't correct
8 Incorrect 394 ms 31472 KB Output isn't correct
9 Correct 256 ms 17452 KB Output is correct