oj.uz

Submission #102298

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

#define INF 999999999

using namespace std;

vector<int> orderNumber;
vector<vector<int> > treeAdj;
vector<int> smallestInSubtree, freePlacesInSubtree, depth, reverseTree;
int n, q;
int root;
int lastRolledDepth;

int computeData(int node, int d, int on){

    int chld = treeAdj[node].size();
    depth[node] = d;
    orderNumber[node] = on;
    //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 on;
    }

    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);
        on = computeData(v, d+1, on+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 on;
}

void fillAllSubtree(int node){
    if(freePlacesInSubtree[node] == 0) return;
    freePlacesInSubtree[node] = 0;
    int sz = treeAdj[node].size();
    for(int i = 0; i < sz; 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; // Won't be needed for "deeper" computation
    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]; // needed for "higher" computation
    }
    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);
    orderNumber.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, 1);

    //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;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Incorrect 281 ms 4472 KB Output isn't correct
3 Incorrect 265 ms 4728 KB Output isn't correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Incorrect 6 ms 384 KB Output isn't correct
9 Incorrect 21 ms 640 KB Output isn't correct
10 Incorrect 51 ms 1408 KB Output isn't correct
11 Incorrect 306 ms 4612 KB Output isn't correct
12 Incorrect 295 ms 4848 KB Output isn't correct
13 Incorrect 323 ms 4616 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 4956 KB Time limit exceeded
2 Execution timed out 1078 ms 14240 KB Time limit exceeded
3 Execution timed out 1074 ms 6900 KB Time limit exceeded
4 Incorrect 300 ms 5180 KB Output isn't correct
5 Execution timed out 1075 ms 5260 KB Time limit exceeded
6 Execution timed out 1056 ms 4876 KB Time limit exceeded
7 Incorrect 707 ms 4116 KB Output isn't correct
8 Execution timed out 1042 ms 4988 KB Time limit exceeded
9 Execution timed out 1056 ms 14328 KB Time limit exceeded
10 Execution timed out 1078 ms 14328 KB Time limit exceeded
11 Execution timed out 1065 ms 14328 KB Time limit exceeded
12 Execution timed out 1064 ms 10232 KB Time limit exceeded
13 Execution timed out 1047 ms 19576 KB Time limit exceeded
14 Execution timed out 1067 ms 6900 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 7628 KB Time limit exceeded
2 Execution timed out 1070 ms 10540 KB Time limit exceeded
3 Execution timed out 1076 ms 17784 KB Time limit exceeded
4 Execution timed out 1055 ms 11556 KB Time limit exceeded
5 Execution timed out 1054 ms 11636 KB Time limit exceeded
6 Execution timed out 1069 ms 11768 KB Time limit exceeded
7 Execution timed out 1071 ms 8780 KB Time limit exceeded
8 Execution timed out 1065 ms 17656 KB Time limit exceeded
9 Execution timed out 1075 ms 14300 KB Time limit exceeded
10 Execution timed out 1078 ms 14392 KB Time limit exceeded
11 Execution timed out 1062 ms 14300 KB Time limit exceeded
12 Execution timed out 1063 ms 10652 KB Time limit exceeded
13 Execution timed out 1049 ms 22136 KB Time limit exceeded
14 Incorrect 302 ms 7272 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 14224 KB Time limit exceeded
2 Execution timed out 1067 ms 10616 KB Time limit exceeded
3 Execution timed out 1076 ms 22108 KB Time limit exceeded
4 Execution timed out 1034 ms 14356 KB Time limit exceeded
5 Execution timed out 1044 ms 14360 KB Time limit exceeded
6 Execution timed out 1060 ms 14260 KB Time limit exceeded
7 Execution timed out 1068 ms 10716 KB Time limit exceeded
8 Execution timed out 1065 ms 22032 KB Time limit exceeded
9 Execution timed out 1080 ms 6900 KB Time limit exceeded