oj.uz

Submission #102299

# Submission time Handle Problem Language Result Execution time Memory
102299 2019-03-24T09:11:49 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
0 / 100
 1000 ms 21624 KB 
#include <bits/stdc++.h>

#define INF 999999999

using namespace std;

vector<vector<int> > treeAdj;
vector<int> smallestInSubtree, freePlacesInSubtree, depth, reverseTree;
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();
    freePlacesInSubtree[node] = 0;
    int v;
    for(int i = 0; i < sz && val > 0; i++){ // The children are sorted by minimum id found in subtree
        v = treeAdj[node][i];
        val = addBalls(v, val);
        freePlacesInSubtree[node]+=freePlacesInSubtree[v];
    }
    return val;
}

void removeBall(int val){
    int index = val;
    int last = index;

    while(true){
        if(freePlacesInSubtree[index] != 0){
            lastRolledDepth = depth[last];
            freePlacesInSubtree[last]++;
            return;
        }
        if(index == root){
            lastRolledDepth = 0;
            freePlacesInSubtree[root]++;
            return;
        }
        last = index;
        index = reverseTree[index];
    }

}

int main()
{
    int p;
    cin >> n >> q;
    depth.resize(n);
    reverseTree.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);
            reverseTree[i] = p-1;
        }
    }

    //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(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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Incorrect 282 ms 4216 KB Output isn't correct
3 Incorrect 253 ms 4308 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 4 ms 384 KB Output isn't correct
6 Incorrect 4 ms 384 KB Output isn't correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Incorrect 5 ms 384 KB Output isn't correct
9 Incorrect 20 ms 512 KB Output isn't correct
10 Incorrect 63 ms 1400 KB Output isn't correct
11 Incorrect 290 ms 4216 KB Output isn't correct
12 Incorrect 262 ms 4488 KB Output isn't correct
13 Incorrect 314 ms 4088 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 4484 KB Time limit exceeded
2 Execution timed out 1074 ms 13808 KB Time limit exceeded
3 Execution timed out 1080 ms 6388 KB Time limit exceeded
4 Incorrect 287 ms 4612 KB Output isn't correct
5 Execution timed out 1068 ms 4604 KB Time limit exceeded
6 Execution timed out 1068 ms 4728 KB Time limit exceeded
7 Incorrect 832 ms 3204 KB Output isn't correct
8 Execution timed out 1075 ms 4348 KB Time limit exceeded
9 Execution timed out 1070 ms 13916 KB Time limit exceeded
10 Execution timed out 1076 ms 13736 KB Time limit exceeded
11 Execution timed out 1074 ms 13688 KB Time limit exceeded
12 Execution timed out 1072 ms 9720 KB Time limit exceeded
13 Execution timed out 1069 ms 19068 KB Time limit exceeded
14 Execution timed out 1083 ms 6388 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 7304 KB Time limit exceeded
2 Execution timed out 1076 ms 10104 KB Time limit exceeded
3 Execution timed out 1077 ms 17400 KB Time limit exceeded
4 Execution timed out 1078 ms 11228 KB Time limit exceeded
5 Execution timed out 1082 ms 11100 KB Time limit exceeded
6 Execution timed out 1070 ms 11128 KB Time limit exceeded
7 Execution timed out 1072 ms 8312 KB Time limit exceeded
8 Execution timed out 1055 ms 17272 KB Time limit exceeded
9 Execution timed out 1072 ms 13944 KB Time limit exceeded
10 Execution timed out 1077 ms 13688 KB Time limit exceeded
11 Execution timed out 1079 ms 13816 KB Time limit exceeded
12 Execution timed out 1076 ms 10132 KB Time limit exceeded
13 Execution timed out 1075 ms 21624 KB Time limit exceeded
14 Incorrect 295 ms 6388 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 13688 KB Time limit exceeded
2 Execution timed out 1062 ms 10156 KB Time limit exceeded
3 Execution timed out 1073 ms 21496 KB Time limit exceeded
4 Execution timed out 1072 ms 13816 KB Time limit exceeded
5 Execution timed out 1063 ms 13772 KB Time limit exceeded
6 Execution timed out 1064 ms 13816 KB Time limit exceeded
7 Execution timed out 1083 ms 10132 KB Time limit exceeded
8 Execution timed out 1069 ms 21540 KB Time limit exceeded
9 Execution timed out 1056 ms 6388 KB Time limit exceeded