oj.uz

Submission #102198

# Submission time Handle Problem Language Result Execution time Memory
102198 2019-03-23T11:28:06 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 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++){ // The children are sorted by minimum id found in subtree
        val = addBalls(treeAdj[node][i], val);
    }
    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
5.76923076923 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Incorrect 284 ms 4344 KB Output isn't correct
3 Correct 281 ms 4364 KB Output is correct
4 Incorrect 2 ms 384 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 4 ms 384 KB Output isn't correct
8 Incorrect 7 ms 384 KB Output isn't correct
9 Incorrect 22 ms 600 KB Output isn't correct
10 Incorrect 59 ms 1312 KB Output isn't correct
11 Incorrect 291 ms 4184 KB Output isn't correct
12 Correct 251 ms 4348 KB Output is correct
13 Incorrect 261 ms 4216 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 4236 KB Time limit exceeded
2 Incorrect 373 ms 14076 KB Output isn't correct
3 Correct 243 ms 6396 KB Output is correct
4 Incorrect 244 ms 4496 KB Output isn't correct
5 Execution timed out 1067 ms 4728 KB Time limit exceeded
6 Incorrect 498 ms 4604 KB Output isn't correct
7 Incorrect 697 ms 3320 KB Output isn't correct
8 Execution timed out 1073 ms 4344 KB Time limit exceeded
9 Incorrect 360 ms 13944 KB Output isn't correct
10 Incorrect 386 ms 13944 KB Output isn't correct
11 Execution timed out 1077 ms 14076 KB Time limit exceeded
12 Execution timed out 1068 ms 10180 KB Time limit exceeded
13 Execution timed out 1066 ms 19040 KB Time limit exceeded
14 Correct 263 ms 6360 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 7164 KB Time limit exceeded
2 Execution timed out 1076 ms 10232 KB Time limit exceeded
3 Execution timed out 1067 ms 17500 KB Time limit exceeded
4 Execution timed out 1070 ms 11104 KB Time limit exceeded
5 Execution timed out 1074 ms 11328 KB Time limit exceeded
6 Execution timed out 1078 ms 11256 KB Time limit exceeded
7 Execution timed out 1054 ms 8240 KB Time limit exceeded
8 Execution timed out 1061 ms 17392 KB Time limit exceeded
9 Execution timed out 1067 ms 13956 KB Time limit exceeded
10 Execution timed out 1071 ms 13728 KB Time limit exceeded
11 Execution timed out 1057 ms 13864 KB Time limit exceeded
12 Execution timed out 1065 ms 10132 KB Time limit exceeded
13 Execution timed out 1075 ms 21624 KB Time limit exceeded
14 Correct 277 ms 6388 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 13856 KB Time limit exceeded
2 Execution timed out 1077 ms 10012 KB Time limit exceeded
3 Execution timed out 1053 ms 21544 KB Time limit exceeded
4 Execution timed out 1062 ms 13732 KB Time limit exceeded
5 Execution timed out 1076 ms 13888 KB Time limit exceeded
6 Execution timed out 1081 ms 13896 KB Time limit exceeded
7 Execution timed out 1071 ms 10124 KB Time limit exceeded
8 Execution timed out 1062 ms 21624 KB Time limit exceeded
9 Correct 242 ms 6388 KB Output is correct