oj.uz

Submission #102192

# Submission time Handle Problem Language Result Execution time Memory
102192 2019-03-23T10:59:17 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
0 / 100
 158 ms 21200 KB 
#include <bits/stdc++.h>

#define INF 999999999

using namespace std;

vector<vector<int> > treeAdj;
vector<int> smallestInSubtree, freePlacesInSubtree, depth;
int n, q;
int root;

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, int *lastRolledDepth){
    if(node == val){
        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, lastRolledDepth);
        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;
    int *lastRolledDepth;
    for(int i = 0; i < q; i++){
        cin >> action >> val;


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

    }


    return 0;
}

Compilation message

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

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Incorrect 82 ms 3704 KB Output isn't correct
3 Incorrect 52 ms 3704 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 2 ms 256 KB Output isn't correct
6 Incorrect 3 ms 384 KB Output isn't correct
7 Incorrect 3 ms 384 KB Output isn't correct
8 Incorrect 2 ms 384 KB Output isn't correct
9 Incorrect 5 ms 512 KB Output isn't correct
10 Incorrect 10 ms 1152 KB Output isn't correct
11 Incorrect 67 ms 3712 KB Output isn't correct
12 Incorrect 48 ms 3676 KB Output isn't correct
13 Incorrect 59 ms 3704 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 4096 KB Output isn't correct
2 Incorrect 103 ms 13304 KB Output isn't correct
3 Incorrect 79 ms 6132 KB Output isn't correct
4 Incorrect 23 ms 4216 KB Output isn't correct
5 Incorrect 30 ms 4216 KB Output isn't correct
6 Incorrect 25 ms 4224 KB Output isn't correct
7 Incorrect 28 ms 2944 KB Output isn't correct
8 Incorrect 16 ms 4096 KB Output isn't correct
9 Incorrect 128 ms 13284 KB Output isn't correct
10 Incorrect 119 ms 13304 KB Output isn't correct
11 Incorrect 122 ms 13372 KB Output isn't correct
12 Incorrect 122 ms 9312 KB Output isn't correct
13 Incorrect 139 ms 18684 KB Output isn't correct
14 Incorrect 95 ms 6004 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 6776 KB Output isn't correct
2 Incorrect 130 ms 9744 KB Output isn't correct
3 Incorrect 103 ms 17016 KB Output isn't correct
4 Incorrect 95 ms 10728 KB Output isn't correct
5 Incorrect 101 ms 10744 KB Output isn't correct
6 Incorrect 95 ms 10744 KB Output isn't correct
7 Incorrect 94 ms 7800 KB Output isn't correct
8 Incorrect 108 ms 16960 KB Output isn't correct
9 Incorrect 117 ms 13304 KB Output isn't correct
10 Incorrect 123 ms 13340 KB Output isn't correct
11 Incorrect 136 ms 13276 KB Output isn't correct
12 Incorrect 145 ms 9592 KB Output isn't correct
13 Incorrect 147 ms 21116 KB Output isn't correct
14 Incorrect 71 ms 6004 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 13304 KB Output isn't correct
2 Incorrect 109 ms 9692 KB Output isn't correct
3 Incorrect 142 ms 21200 KB Output isn't correct
4 Incorrect 123 ms 13404 KB Output isn't correct
5 Incorrect 125 ms 13432 KB Output isn't correct
6 Incorrect 158 ms 13264 KB Output isn't correct
7 Incorrect 148 ms 9592 KB Output isn't correct
8 Incorrect 136 ms 21108 KB Output isn't correct
9 Incorrect 84 ms 6004 KB Output isn't correct