oj.uz

Submission #102191

# Submission time Handle Problem Language Result Execution time Memory
102191 2019-03-23T10:58:39 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
0 / 100
 99 ms 6904 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 256 KB Output isn't correct
2 Incorrect 35 ms 3704 KB Output isn't correct
3 Incorrect 38 ms 3704 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Incorrect 2 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 4 ms 512 KB Output isn't correct
10 Incorrect 9 ms 1152 KB Output isn't correct
11 Incorrect 44 ms 3644 KB Output isn't correct
12 Incorrect 36 ms 3680 KB Output isn't correct
13 Incorrect 38 ms 3704 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 1536 KB Output isn't correct
2 Incorrect 65 ms 5752 KB Output isn't correct
3 Incorrect 53 ms 5236 KB Output isn't correct
4 Incorrect 19 ms 2176 KB Output isn't correct
5 Incorrect 17 ms 1916 KB Output isn't correct
6 Incorrect 20 ms 1920 KB Output isn't correct
7 Incorrect 16 ms 1792 KB Output isn't correct
8 Incorrect 10 ms 1536 KB Output isn't correct
9 Incorrect 64 ms 6296 KB Output isn't correct
10 Incorrect 61 ms 5880 KB Output isn't correct
11 Incorrect 64 ms 5752 KB Output isn't correct
12 Incorrect 57 ms 5752 KB Output isn't correct
13 Incorrect 53 ms 6136 KB Output isn't correct
14 Incorrect 59 ms 5236 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 3200 KB Output isn't correct
2 Incorrect 57 ms 5860 KB Output isn't correct
3 Incorrect 48 ms 5632 KB Output isn't correct
4 Incorrect 55 ms 5052 KB Output isn't correct
5 Incorrect 44 ms 4728 KB Output isn't correct
6 Incorrect 49 ms 4784 KB Output isn't correct
7 Incorrect 59 ms 4728 KB Output isn't correct
8 Incorrect 50 ms 5624 KB Output isn't correct
9 Incorrect 70 ms 6264 KB Output isn't correct
10 Incorrect 73 ms 5752 KB Output isn't correct
11 Incorrect 57 ms 5752 KB Output isn't correct
12 Incorrect 65 ms 5880 KB Output isn't correct
13 Incorrect 99 ms 6904 KB Output isn't correct
14 Incorrect 81 ms 5236 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 6196 KB Output isn't correct
2 Incorrect 67 ms 5780 KB Output isn't correct
3 Incorrect 60 ms 6904 KB Output isn't correct
4 Incorrect 65 ms 6296 KB Output isn't correct
5 Incorrect 94 ms 5880 KB Output isn't correct
6 Incorrect 57 ms 5880 KB Output isn't correct
7 Incorrect 62 ms 5752 KB Output isn't correct
8 Incorrect 58 ms 6904 KB Output isn't correct
9 Incorrect 56 ms 5240 KB Output isn't correct