oj.uz

Submission #102303

# Submission time Handle Problem Language Result Execution time Memory
102303 2019-03-24T09:24:30 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
4.78022 / 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 toPlace){ // returns new val after filling subtree of node
    if(toPlace == 0 || freePlacesInSubtree[node] <= 0) return toPlace;

    int freePlaces = freePlacesInSubtree[node];

    if(freePlaces < toPlace){
        fillAllSubtree(node);
        return toPlace-freePlaces;
    }
    else if(freePlaces == toPlace){
        // 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, placed;
    for(int i = 0; i < sz && toPlace > 0; i++){ // The children are sorted by minimum id found in subtree
        v = treeAdj[node][i];
        placed = toPlace-addBalls(v, toPlace);
        freePlacesInSubtree[node]-=placed;
        toPlace = toPlace-placed;
        //freePlacesInSubtree[node]+=freePlacesInSubtree[v];
    }
    return toPlace;
}

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
1.92307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Incorrect 306 ms 4264 KB Output isn't correct
3 Incorrect 249 ms 4344 KB Output isn't correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Incorrect 3 ms 384 KB Output isn't correct
6 Correct 3 ms 384 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Incorrect 5 ms 384 KB Output isn't correct
9 Incorrect 18 ms 640 KB Output isn't correct
10 Incorrect 65 ms 1280 KB Output isn't correct
11 Incorrect 275 ms 4216 KB Output isn't correct
12 Incorrect 254 ms 4472 KB Output isn't correct
13 Incorrect 286 ms 4216 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 4360 KB Time limit exceeded
2 Execution timed out 1080 ms 13816 KB Time limit exceeded
3 Incorrect 244 ms 6388 KB Output isn't correct
4 Incorrect 251 ms 4640 KB Output isn't correct
5 Execution timed out 1070 ms 4768 KB Time limit exceeded
6 Execution timed out 1068 ms 4700 KB Time limit exceeded
7 Incorrect 719 ms 3356 KB Output isn't correct
8 Execution timed out 1082 ms 4472 KB Time limit exceeded
9 Execution timed out 1069 ms 13944 KB Time limit exceeded
10 Execution timed out 1080 ms 14072 KB Time limit exceeded
11 Execution timed out 1075 ms 13816 KB Time limit exceeded
12 Execution timed out 1075 ms 10124 KB Time limit exceeded
13 Execution timed out 1081 ms 18936 KB Time limit exceeded
14 Incorrect 249 ms 6388 KB Output isn't correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 7160 KB Time limit exceeded
2 Execution timed out 1087 ms 10332 KB Time limit exceeded
3 Execution timed out 1073 ms 17400 KB Time limit exceeded
4 Execution timed out 1087 ms 11128 KB Time limit exceeded
5 Execution timed out 1069 ms 11128 KB Time limit exceeded
6 Execution timed out 1071 ms 11132 KB Time limit exceeded
7 Execution timed out 1082 ms 8284 KB Time limit exceeded
8 Execution timed out 1055 ms 17504 KB Time limit exceeded
9 Execution timed out 1069 ms 13816 KB Time limit exceeded
10 Execution timed out 1065 ms 13860 KB Time limit exceeded
11 Execution timed out 1056 ms 13940 KB Time limit exceeded
12 Execution timed out 1059 ms 10080 KB Time limit exceeded
13 Execution timed out 1082 ms 21624 KB Time limit exceeded
14 Correct 302 ms 6516 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 13840 KB Time limit exceeded
2 Execution timed out 1066 ms 10164 KB Time limit exceeded
3 Execution timed out 1091 ms 21496 KB Time limit exceeded
4 Execution timed out 1062 ms 14072 KB Time limit exceeded
5 Execution timed out 1063 ms 13916 KB Time limit exceeded
6 Execution timed out 1074 ms 13896 KB Time limit exceeded
7 Execution timed out 1083 ms 10236 KB Time limit exceeded
8 Execution timed out 1083 ms 21500 KB Time limit exceeded
9 Incorrect 286 ms 6388 KB Output isn't correct