oj.uz

Submission #102194

# Submission time Handle Problem Language Result Execution time Memory
102194 2019-03-23T11:01:28 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
0 / 100
 1000 ms 21136 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{
            continue;
            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 95 ms 3712 KB Output isn't correct
3 Execution timed out 1073 ms 3964 KB Time limit exceeded
4 Incorrect 2 ms 256 KB Output isn't correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Incorrect 3 ms 384 KB Output isn't correct
7 Incorrect 2 ms 384 KB Output isn't correct
8 Incorrect 3 ms 384 KB Output isn't correct
9 Incorrect 7 ms 512 KB Output isn't correct
10 Incorrect 33 ms 1152 KB Output isn't correct
11 Incorrect 113 ms 3704 KB Output isn't correct
12 Execution timed out 1074 ms 3960 KB Time limit exceeded
13 Incorrect 104 ms 3708 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 4096 KB Time limit exceeded
2 Incorrect 184 ms 13492 KB Output isn't correct
3 Execution timed out 1076 ms 6004 KB Time limit exceeded
4 Incorrect 77 ms 4216 KB Output isn't correct
5 Incorrect 88 ms 4316 KB Output isn't correct
6 Incorrect 97 ms 4220 KB Output isn't correct
7 Incorrect 56 ms 2816 KB Output isn't correct
8 Execution timed out 1079 ms 4096 KB Time limit exceeded
9 Incorrect 189 ms 13264 KB Output isn't correct
10 Incorrect 192 ms 13308 KB Output isn't correct
11 Execution timed out 1070 ms 13376 KB Time limit exceeded
12 Incorrect 185 ms 9464 KB Output isn't correct
13 Execution timed out 1078 ms 18680 KB Time limit exceeded
14 Execution timed out 1060 ms 6004 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 6828 KB Output isn't correct
2 Incorrect 206 ms 9592 KB Output isn't correct
3 Incorrect 169 ms 17016 KB Output isn't correct
4 Incorrect 127 ms 10744 KB Output isn't correct
5 Incorrect 125 ms 10760 KB Output isn't correct
6 Incorrect 119 ms 10744 KB Output isn't correct
7 Incorrect 128 ms 7788 KB Output isn't correct
8 Incorrect 151 ms 16888 KB Output isn't correct
9 Incorrect 193 ms 13560 KB Output isn't correct
10 Incorrect 173 ms 13304 KB Output isn't correct
11 Incorrect 152 ms 13304 KB Output isn't correct
12 Incorrect 206 ms 9724 KB Output isn't correct
13 Incorrect 211 ms 21136 KB Output isn't correct
14 Incorrect 130 ms 6004 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 13432 KB Output isn't correct
2 Incorrect 159 ms 9592 KB Output isn't correct
3 Execution timed out 1076 ms 21100 KB Time limit exceeded
4 Incorrect 189 ms 13304 KB Output isn't correct
5 Incorrect 188 ms 13432 KB Output isn't correct
6 Execution timed out 1072 ms 13336 KB Time limit exceeded
7 Incorrect 171 ms 9628 KB Output isn't correct
8 Execution timed out 1079 ms 21112 KB Time limit exceeded
9 Execution timed out 1074 ms 5972 KB Time limit exceeded