oj.uz

답안 #102359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102359 2019-03-24T13:33:11 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
81.1905 / 100
 1000 ms 31576 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){
    int maxJump = depth[node];
    int minJump = 0;
    int md, 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 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
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 336 ms 11636 KB Output is correct
3 Correct 230 ms 11636 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 22 ms 1024 KB Output is correct
10 Correct 66 ms 2932 KB Output is correct
11 Correct 364 ms 11512 KB Output is correct
12 Correct 261 ms 11636 KB Output is correct
13 Correct 335 ms 11508 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 6504 KB Output is correct
2 Correct 710 ms 23856 KB Output is correct
3 Correct 308 ms 17304 KB Output is correct
4 Correct 250 ms 7672 KB Output is correct
5 Correct 298 ms 7672 KB Output is correct
6 Correct 380 ms 7668 KB Output is correct
7 Correct 295 ms 6372 KB Output is correct
8 Correct 173 ms 6392 KB Output is correct
9 Correct 594 ms 24308 KB Output is correct
10 Correct 735 ms 23988 KB Output is correct
11 Correct 582 ms 23888 KB Output is correct
12 Correct 655 ms 20152 KB Output is correct
13 Correct 533 ms 28020 KB Output is correct
14 Correct 260 ms 17404 KB Output is correct

Subtask #3
22.8571428571 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 340 ms 12464 KB Output is correct
2 Execution timed out 1062 ms 20924 KB Time limit exceeded
3 Correct 847 ms 25328 KB Output is correct
4 Correct 555 ms 19700 KB Output is correct
5 Correct 616 ms 19220 KB Output is correct
6 Correct 682 ms 19488 KB Output is correct
7 Correct 601 ms 16860 KB Output is correct
8 Execution timed out 1062 ms 25284 KB Time limit exceeded
9 Correct 973 ms 24436 KB Output is correct
10 Execution timed out 1056 ms 24060 KB Time limit exceeded
11 Execution timed out 1076 ms 24080 KB Time limit exceeded
12 Execution timed out 1066 ms 21080 KB Time limit exceeded
13 Execution timed out 1082 ms 31340 KB Time limit exceeded
14 Correct 305 ms 17356 KB Output is correct

Subtask #4
3.33333333333 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1062 ms 24660 KB Time limit exceeded
2 Execution timed out 1054 ms 20956 KB Time limit exceeded
3 Correct 507 ms 31576 KB Output is correct
4 Correct 946 ms 24672 KB Output is correct
5 Execution timed out 1062 ms 24108 KB Time limit exceeded
6 Correct 616 ms 23860 KB Output is correct
7 Correct 969 ms 20952 KB Output is correct
8 Correct 502 ms 31560 KB Output is correct
9 Correct 250 ms 17256 KB Output is correct