oj.uz

Submission #102304

# Submission time Handle Problem Language Result Execution time Memory
102304 2019-03-24T09:25:51 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
13.4676 / 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
5.76923076923 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Incorrect 305 ms 4216 KB Output isn't correct
3 Correct 269 ms 4512 KB Output is correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Correct 5 ms 384 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Incorrect 6 ms 512 KB Output isn't correct
9 Incorrect 23 ms 640 KB Output isn't correct
10 Incorrect 54 ms 1400 KB Output isn't correct
11 Incorrect 304 ms 4216 KB Output isn't correct
12 Correct 254 ms 4336 KB Output is correct
13 Incorrect 328 ms 4228 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 4472 KB Time limit exceeded
2 Incorrect 382 ms 14072 KB Output isn't correct
3 Correct 301 ms 6388 KB Output is correct
4 Incorrect 305 ms 4612 KB Output isn't correct
5 Execution timed out 1067 ms 4616 KB Time limit exceeded
6 Incorrect 563 ms 4736 KB Output isn't correct
7 Incorrect 790 ms 3332 KB Output isn't correct
8 Execution timed out 1066 ms 4344 KB Time limit exceeded
9 Incorrect 384 ms 13940 KB Output isn't correct
10 Incorrect 370 ms 13944 KB Output isn't correct
11 Execution timed out 1080 ms 14084 KB Time limit exceeded
12 Execution timed out 1058 ms 10040 KB Time limit exceeded
13 Execution timed out 1075 ms 19064 KB Time limit exceeded
14 Correct 262 ms 6388 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 7432 KB Time limit exceeded
2 Execution timed out 1074 ms 10244 KB Time limit exceeded
3 Execution timed out 1074 ms 17400 KB Time limit exceeded
4 Execution timed out 1063 ms 11256 KB Time limit exceeded
5 Execution timed out 1069 ms 11256 KB Time limit exceeded
6 Execution timed out 1054 ms 11204 KB Time limit exceeded
7 Execution timed out 1054 ms 8440 KB Time limit exceeded
8 Execution timed out 1072 ms 17400 KB Time limit exceeded
9 Execution timed out 1074 ms 13816 KB Time limit exceeded
10 Execution timed out 1073 ms 13916 KB Time limit exceeded
11 Execution timed out 1068 ms 13976 KB Time limit exceeded
12 Execution timed out 1070 ms 10128 KB Time limit exceeded
13 Execution timed out 1071 ms 21624 KB Time limit exceeded
14 Correct 298 ms 6388 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 13944 KB Time limit exceeded
2 Execution timed out 1066 ms 9992 KB Time limit exceeded
3 Execution timed out 1079 ms 21496 KB Time limit exceeded
4 Execution timed out 1078 ms 13840 KB Time limit exceeded
5 Execution timed out 1074 ms 13944 KB Time limit exceeded
6 Execution timed out 1065 ms 14072 KB Time limit exceeded
7 Execution timed out 1075 ms 10248 KB Time limit exceeded
8 Execution timed out 1078 ms 21624 KB Time limit exceeded
9 Correct 257 ms 6388 KB Output is correct