oj.uz

Submission #102379

# Submission time Handle Problem Language Result Execution time Memory
102379 2019-03-24T14:49:22 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
46.7643 / 100
 640 ms 31560 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 = jumpTable[0].size()-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 3 ms 384 KB Output isn't correct
2 Incorrect 321 ms 11508 KB Output isn't correct
3 Incorrect 235 ms 11820 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 Correct 4 ms 512 KB Output is correct
7 Incorrect 4 ms 512 KB Output isn't correct
8 Incorrect 4 ms 512 KB Output isn't correct
9 Incorrect 19 ms 1024 KB Output isn't correct
10 Incorrect 64 ms 2924 KB Output isn't correct
11 Incorrect 315 ms 11508 KB Output isn't correct
12 Incorrect 322 ms 11732 KB Output isn't correct
13 Incorrect 283 ms 11504 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 160 ms 6520 KB Output isn't correct
2 Incorrect 517 ms 23884 KB Output isn't correct
3 Correct 277 ms 17352 KB Output is correct
4 Incorrect 197 ms 7672 KB Output isn't correct
5 Incorrect 244 ms 7780 KB Output isn't correct
6 Incorrect 233 ms 7668 KB Output isn't correct
7 Incorrect 241 ms 6220 KB Output isn't correct
8 Incorrect 198 ms 6364 KB Output isn't correct
9 Incorrect 444 ms 24304 KB Output isn't correct
10 Incorrect 535 ms 23900 KB Output isn't correct
11 Incorrect 435 ms 23840 KB Output isn't correct
12 Incorrect 404 ms 20236 KB Output isn't correct
13 Incorrect 383 ms 27892 KB Output isn't correct
14 Correct 247 ms 17416 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 12404 KB Output is correct
2 Correct 471 ms 21008 KB Output is correct
3 Correct 399 ms 25276 KB Output is correct
4 Correct 322 ms 19696 KB Output is correct
5 Correct 307 ms 19332 KB Output is correct
6 Correct 296 ms 19228 KB Output is correct
7 Correct 352 ms 16800 KB Output is correct
8 Correct 413 ms 25356 KB Output is correct
9 Correct 450 ms 24428 KB Output is correct
10 Correct 454 ms 23992 KB Output is correct
11 Correct 471 ms 24080 KB Output is correct
12 Correct 445 ms 20880 KB Output is correct
13 Correct 640 ms 31560 KB Output is correct
14 Correct 388 ms 17284 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 551 ms 24440 KB Output isn't correct
2 Incorrect 449 ms 20756 KB Output isn't correct
3 Incorrect 456 ms 31492 KB Output isn't correct
4 Incorrect 487 ms 24488 KB Output isn't correct
5 Incorrect 507 ms 23984 KB Output isn't correct
6 Incorrect 454 ms 23920 KB Output isn't correct
7 Incorrect 541 ms 20976 KB Output isn't correct
8 Incorrect 474 ms 31472 KB Output isn't correct
9 Correct 273 ms 17384 KB Output is correct