Submission #102195

#	Time	Username	Problem	Language	Result	Execution time	Memory
102195		TomGautot	Ball Machine (BOI13_ballmachine)	C++14	10.61 / 100	1088 ms	21112 KiB

ballmachine

#include <bits/stdc++.h>

#define INF 999999999

using namespace std;

vector<vector<int> > treeAdj;
vector<int> smallestInSubtree, freePlacesInSubtree, depth;
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;
}

void fillAllSubtree(int node){
    if(freePlacesInSubtree[node] == 0) return;
    freePlacesInSubtree[node] = 0;
    for(int i = 0; i < treeAdj[node].size(); i++){
        fillAllSubtree(treeAdj[node][i]);
    }
}

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

    int freePlaces = freePlacesInSubtree[node];

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

    int sz = treeAdj[node].size();
    for(int i = 0; i < sz && val > 0; i++){
        val = addBalls(treeAdj[node][i], val);
    }
    return val;
}

int removeBall(int node, int val){
    if(node == val){
        if(node == root){
            freePlacesInSubtree[root]++;
            lastRolledDepth = 0;
            return 2;
        }
        return 1;
    }
    int sz = treeAdj[node].size();
    if(sz == 0){
        return 0;
    }

    bool nodeIsFree = freePlacesInSubtree[node] != 0;

    //cout << "Is node " << node << " free " << (nodeIsFree?"1":"0") << endl;

    int returnCode, v;
    for(int i = 0; i < sz; i++){
        v = treeAdj[node][i];
        returnCode = removeBall(v, val);
        if(returnCode == 1){
            if(!nodeIsFree){
                if(node == root){
                    freePlacesInSubtree[root]++;
                    lastRolledDepth = 0;
                    return 2;
                }
                else return 1;
            }
            freePlacesInSubtree[v]++;
            lastRolledDepth = depth[v];
            return 2;
        }
        if(returnCode == 2) return 2;
    }

    return 0;

}

int main()
{
    int p;
    cin >> n >> q;
    depth.resize(n);
    treeAdj.resize(n);
    smallestInSubtree.resize(n);
    freePlacesInSubtree.resize(n);
    for(int i = 0; i < n; i++){
        cin >> p;
        if(p == 0) root = i;
        else{
            treeAdj[p-1].push_back(i);
        }
    }

    //cout << "Going to compute data" << endl;

    //return 0;

    computeData(root, 0);

    //return 0;
    //cout << "Data was computedd successfully" << endl;

    int action, val;
    for(int i = 0; i < q; i++){
        cin >> action >> val;


        if(action == 1){
            addBalls(root, val);
        }
        else{
            val--;
            removeBall(root, val);
            //cout << "Last rolled depth is " << *lastRolledDepth << endl;
            cout << depth[val] - lastRolledDepth << endl;
        }

    }


    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void fillAllSubtree(int)':
ballmachine.cpp:55:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < treeAdj[node].size(); i++){
                    ~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5.769230769230769 / 25
• Subtask 2: 4.285714285714286 / 30
• Subtask 3: 0 / 40
• Subtask 4: 0.5555555555555556 / 5