oj.uz

Submission #102300

# Submission time Handle Problem Language Result Execution time Memory
102300 2019-03-24T09:13:22 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
13.4676 / 100
 1000 ms 21596 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
5.76923076923 / 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 Correct 237 ms 4344 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Correct 3 ms 384 KB Output is correct
7 Incorrect 6 ms 384 KB Output isn't correct
8 Incorrect 5 ms 384 KB Output isn't correct
9 Incorrect 24 ms 512 KB Output isn't correct
10 Incorrect 66 ms 1260 KB Output isn't correct
11 Incorrect 351 ms 4120 KB Output isn't correct
12 Correct 249 ms 4348 KB Output is correct
13 Incorrect 290 ms 4232 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 4236 KB Time limit exceeded
2 Incorrect 409 ms 14468 KB Output isn't correct
3 Correct 287 ms 6388 KB Output is correct
4 Incorrect 262 ms 4472 KB Output isn't correct
5 Execution timed out 1078 ms 4728 KB Time limit exceeded
6 Incorrect 489 ms 4900 KB Output isn't correct
7 Incorrect 813 ms 3320 KB Output isn't correct
8 Execution timed out 1078 ms 4300 KB Time limit exceeded
9 Incorrect 372 ms 14588 KB Output isn't correct
10 Incorrect 395 ms 14456 KB Output isn't correct
11 Execution timed out 1078 ms 14200 KB Time limit exceeded
12 Execution timed out 1054 ms 10648 KB Time limit exceeded
13 Execution timed out 1065 ms 19064 KB Time limit exceeded
14 Correct 289 ms 6392 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 7204 KB Time limit exceeded
2 Execution timed out 1069 ms 10232 KB Time limit exceeded
3 Execution timed out 1068 ms 17300 KB Time limit exceeded
4 Execution timed out 1068 ms 11000 KB Time limit exceeded
5 Execution timed out 1076 ms 11128 KB Time limit exceeded
6 Execution timed out 1065 ms 11256 KB Time limit exceeded
7 Execution timed out 1076 ms 8312 KB Time limit exceeded
8 Execution timed out 1072 ms 17400 KB Time limit exceeded
9 Execution timed out 1078 ms 13816 KB Time limit exceeded
10 Execution timed out 1083 ms 13816 KB Time limit exceeded
11 Execution timed out 1070 ms 13832 KB Time limit exceeded
12 Execution timed out 1067 ms 10164 KB Time limit exceeded
13 Execution timed out 1082 ms 21596 KB Time limit exceeded
14 Correct 293 ms 6388 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 14008 KB Time limit exceeded
2 Execution timed out 1062 ms 10024 KB Time limit exceeded
3 Execution timed out 1080 ms 21496 KB Time limit exceeded
4 Execution timed out 1080 ms 14072 KB Time limit exceeded
5 Execution timed out 1075 ms 14072 KB Time limit exceeded
6 Execution timed out 1068 ms 14228 KB Time limit exceeded
7 Execution timed out 1077 ms 10152 KB Time limit exceeded
8 Execution timed out 1078 ms 21496 KB Time limit exceeded
9 Correct 266 ms 6388 KB Output is correct