oj.uz

Submission #102378

# Submission time Handle Problem Language Result Execution time Memory
102378 2019-03-24T14:47:22 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
46.7643 / 100
 574 ms 31604 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;
int maxBinaryJump;

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 = maxBinaryJump-1;

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

    for(int i = p; i >= 0; i--){
        if(jumpTable[node][i] < 0) continue;
      //      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);
    maxBinaryJump = log2(n)+1;
    for(int i = 0; i < n; i++){
        jumpTable[i].assign(maxBinaryJump, -1);
        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 removeBallWithPQ(int)':
ballmachine.cpp:144:9: warning: unused variable 'maxJump' [-Wunused-variable]
     int maxJump = depth[node];
         ^~~~~~~
ballmachine.cpp: In function 'void addBallsWithPQ(int)':
ballmachine.cpp:126:9: warning: 'spot' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int spot;
         ^~~~

Subtask #1
1.92307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Incorrect 280 ms 11524 KB Output isn't correct
3 Incorrect 268 ms 11700 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Correct 4 ms 516 KB Output is correct
7 Incorrect 5 ms 512 KB Output isn't correct
8 Incorrect 6 ms 560 KB Output isn't correct
9 Incorrect 17 ms 1024 KB Output isn't correct
10 Incorrect 44 ms 2936 KB Output isn't correct
11 Incorrect 311 ms 11504 KB Output isn't correct
12 Incorrect 243 ms 11768 KB Output isn't correct
13 Incorrect 294 ms 11552 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 6348 KB Output isn't correct
2 Incorrect 461 ms 23900 KB Output isn't correct
3 Correct 242 ms 17236 KB Output is correct
4 Incorrect 222 ms 7672 KB Output isn't correct
5 Incorrect 224 ms 7668 KB Output isn't correct
6 Incorrect 231 ms 7604 KB Output isn't correct
7 Incorrect 255 ms 6236 KB Output isn't correct
8 Incorrect 158 ms 6336 KB Output isn't correct
9 Incorrect 390 ms 24308 KB Output isn't correct
10 Incorrect 434 ms 24024 KB Output isn't correct
11 Incorrect 396 ms 23856 KB Output isn't correct
12 Incorrect 422 ms 20324 KB Output isn't correct
13 Incorrect 400 ms 27892 KB Output isn't correct
14 Correct 285 ms 17384 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 12404 KB Output is correct
2 Correct 460 ms 20876 KB Output is correct
3 Correct 390 ms 25328 KB Output is correct
4 Correct 329 ms 19564 KB Output is correct
5 Correct 321 ms 19336 KB Output is correct
6 Correct 283 ms 19192 KB Output is correct
7 Correct 342 ms 16736 KB Output is correct
8 Correct 353 ms 25332 KB Output is correct
9 Correct 517 ms 24364 KB Output is correct
10 Correct 489 ms 23992 KB Output is correct
11 Correct 493 ms 24004 KB Output is correct
12 Correct 401 ms 20860 KB Output is correct
13 Correct 553 ms 31604 KB Output is correct
14 Correct 324 ms 17304 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 574 ms 24440 KB Output isn't correct
2 Incorrect 480 ms 20812 KB Output isn't correct
3 Incorrect 414 ms 31604 KB Output isn't correct
4 Incorrect 497 ms 24568 KB Output isn't correct
5 Incorrect 523 ms 23988 KB Output isn't correct
6 Incorrect 477 ms 23972 KB Output isn't correct
7 Incorrect 443 ms 20756 KB Output isn't correct
8 Incorrect 461 ms 31544 KB Output isn't correct
9 Correct 279 ms 17512 KB Output is correct