oj.uz

Submission #102195

# Submission time Handle Problem Language Result Execution time Memory
102195 2019-03-23T11:05:23 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
10.6105 / 100
 1000 ms 21112 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;
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

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.76923076923 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Execution timed out 1079 ms 3760 KB Time limit exceeded
3 Correct 284 ms 4128 KB Output is correct
4 Incorrect 3 ms 256 KB Output isn't correct
5 Incorrect 3 ms 384 KB Output isn't correct
6 Correct 5 ms 384 KB Output is correct
7 Incorrect 8 ms 384 KB Output isn't correct
8 Incorrect 9 ms 384 KB Output isn't correct
9 Incorrect 181 ms 612 KB Output isn't correct
10 Execution timed out 1077 ms 1400 KB Time limit exceeded
11 Execution timed out 1071 ms 3704 KB Time limit exceeded
12 Correct 272 ms 4052 KB Output is correct
13 Execution timed out 1080 ms 3892 KB Time limit exceeded

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 4224 KB Time limit exceeded
2 Execution timed out 1075 ms 13372 KB Time limit exceeded
3 Correct 290 ms 6104 KB Output is correct
4 Execution timed out 1076 ms 4344 KB Time limit exceeded
5 Execution timed out 1071 ms 4224 KB Time limit exceeded
6 Execution timed out 1062 ms 4216 KB Time limit exceeded
7 Execution timed out 1076 ms 2944 KB Time limit exceeded
8 Execution timed out 1070 ms 4096 KB Time limit exceeded
9 Execution timed out 1072 ms 13304 KB Time limit exceeded
10 Execution timed out 1062 ms 13392 KB Time limit exceeded
11 Execution timed out 1070 ms 13304 KB Time limit exceeded
12 Execution timed out 1079 ms 9336 KB Time limit exceeded
13 Execution timed out 1075 ms 18808 KB Time limit exceeded
14 Correct 260 ms 6132 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 6776 KB Time limit exceeded
2 Execution timed out 1088 ms 9592 KB Time limit exceeded
3 Execution timed out 1076 ms 17084 KB Time limit exceeded
4 Execution timed out 1084 ms 10744 KB Time limit exceeded
5 Execution timed out 1073 ms 10744 KB Time limit exceeded
6 Execution timed out 1076 ms 10744 KB Time limit exceeded
7 Execution timed out 1077 ms 7672 KB Time limit exceeded
8 Execution timed out 1072 ms 17016 KB Time limit exceeded
9 Execution timed out 1075 ms 13304 KB Time limit exceeded
10 Execution timed out 1050 ms 13404 KB Time limit exceeded
11 Execution timed out 1076 ms 13304 KB Time limit exceeded
12 Execution timed out 1066 ms 9592 KB Time limit exceeded
13 Execution timed out 1065 ms 21108 KB Time limit exceeded
14 Execution timed out 1069 ms 6004 KB Time limit exceeded

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 13280 KB Time limit exceeded
2 Execution timed out 1085 ms 9592 KB Time limit exceeded
3 Execution timed out 1083 ms 20984 KB Time limit exceeded
4 Execution timed out 1069 ms 13304 KB Time limit exceeded
5 Execution timed out 1072 ms 13404 KB Time limit exceeded
6 Execution timed out 1067 ms 13264 KB Time limit exceeded
7 Execution timed out 1060 ms 9592 KB Time limit exceeded
8 Execution timed out 1082 ms 21112 KB Time limit exceeded
9 Correct 273 ms 6004 KB Output is correct