oj.uz

답안 #102335

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102335 2019-03-24T10:56:11 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
60.0794 / 100
 1000 ms 23280 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<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 fillAllSubtree(int node){
    if(freePlacesInSubtree[node] == 0) return;
    freePlacesInSubtree[node] = 0;
    int sz = treeAdj[node].size();
    for(int i = 0; i < sz; i++){
        fillAllSubtree(treeAdj[node][i]);
    }
}

int addBalls(int node, int toPlace){ // returns new val after filling subtree of node
    if(toPlace == 0 || freePlacesInSubtree[node] <= 0) return toPlace;

    int freePlaces = freePlacesInSubtree[node];

    if(freePlaces < toPlace){
        fillAllSubtree(node);
        return toPlace-freePlaces;
    }
    else if(freePlaces == toPlace){
        // This node is the one to be output
        fillAllSubtree(node);
        cout << node+1 << endl;
        return 0;
    }

    int sz = treeAdj[node].size();
    //freePlacesInSubtree[node] = 0;
    int v, placed;
    for(int i = 0; i < sz && toPlace > 0; i++){ // The children are sorted by minimum id found in subtree
        v = treeAdj[node][i];
        placed = toPlace-addBalls(v, toPlace);
        freePlacesInSubtree[node]-=placed;
        toPlace = toPlace-placed;
        //freePlacesInSubtree[node]+=freePlacesInSubtree[v];
    }

    //cout << "There are now " << freePlacesInSubtree[node] << " in the subtree of " << node << endl;

    return toPlace;
}

void removeBall(int val){
    int index = val;
    int last = index;
    bool addMode = false;

    while(true){
        if(addMode){
            freePlacesInSubtree[index]++;
            if(index == root) return;
        }
        else if(freePlacesInSubtree[index] != 0){
            lastRolledDepth = depth[last];
            freePlacesInSubtree[last]++;
            addMode = true;
            continue;
        }
        else if(index == root){
            lastRolledDepth = depth[root];
            freePlacesInSubtree[root]++;
            return;
        }
        last = index;
        index = reverseTree[index];
    }

}

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("\nfpist: ");

    for(int i = 0; i < n; i++){
        printf("%d ", freePlacesInSubtree[i]);
    }
    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 val){
    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);
    available.assign(n, true);
    for(int i = 0; i < n; i++){
        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);

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

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 234 ms 5112 KB Output is correct
3 Correct 180 ms 5368 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 24 ms 680 KB Output is correct
10 Correct 51 ms 1536 KB Output is correct
11 Correct 271 ms 5120 KB Output is correct
12 Correct 195 ms 5352 KB Output is correct
13 Correct 294 ms 5360 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 4856 KB Output is correct
2 Correct 315 ms 14904 KB Output is correct
3 Correct 238 ms 7532 KB Output is correct
4 Correct 157 ms 4984 KB Output is correct
5 Correct 173 ms 4848 KB Output is correct
6 Correct 151 ms 4852 KB Output is correct
7 Correct 157 ms 3576 KB Output is correct
8 Correct 156 ms 4984 KB Output is correct
9 Correct 289 ms 15228 KB Output is correct
10 Correct 282 ms 14792 KB Output is correct
11 Correct 275 ms 14896 KB Output is correct
12 Correct 313 ms 11032 KB Output is correct
13 Correct 341 ms 20696 KB Output is correct
14 Correct 255 ms 7524 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1067 ms 8064 KB Time limit exceeded
2 Execution timed out 1068 ms 11276 KB Time limit exceeded
3 Execution timed out 1083 ms 18524 KB Time limit exceeded
4 Execution timed out 1081 ms 12400 KB Time limit exceeded
5 Execution timed out 1077 ms 12084 KB Time limit exceeded
6 Execution timed out 1083 ms 12052 KB Time limit exceeded
7 Execution timed out 1080 ms 9280 KB Time limit exceeded
8 Execution timed out 1058 ms 18552 KB Time limit exceeded
9 Execution timed out 1084 ms 15220 KB Time limit exceeded
10 Execution timed out 1065 ms 14780 KB Time limit exceeded
11 Execution timed out 1061 ms 14908 KB Time limit exceeded
12 Execution timed out 1071 ms 11404 KB Time limit exceeded
13 Execution timed out 1075 ms 23068 KB Time limit exceeded
14 Correct 250 ms 7656 KB Output is correct

Subtask #4
2.22222222222 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1066 ms 15204 KB Time limit exceeded
2 Execution timed out 1080 ms 11380 KB Time limit exceeded
3 Correct 302 ms 23280 KB Output is correct
4 Execution timed out 1075 ms 15096 KB Time limit exceeded
5 Execution timed out 1080 ms 14904 KB Time limit exceeded
6 Correct 359 ms 14996 KB Output is correct
7 Execution timed out 1058 ms 11156 KB Time limit exceeded
8 Correct 301 ms 23192 KB Output is correct
9 Correct 241 ms 7628 KB Output is correct