oj.uz

Submission #102322

# Submission time Handle Problem Language Result Execution time Memory
102322 2019-03-24T10:23:16 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
32.6984 / 100
 1000 ms 21568 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;
    int sz = treeAdj[node].size();
    for(int i = 0; i < sz; 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];
    }

    //cout << "There are now " << freePlacesInSubtree[node] << " in the subtree of " << node << endl;

    return toPlace;
}

void removeBall(int val){
    int index = val;
    int last = index;
    bool addMode = false;

    while(true){
        if(addMode){
            freePlacesInSubtree[index]++;
            if(index == root) return;
        }
        else if(freePlacesInSubtree[index] != 0){
            lastRolledDepth = depth[last];
            freePlacesInSubtree[last]++;
            addMode = true;
            continue;
        }
        else if(index == root){
            lastRolledDepth = depth[root];
            freePlacesInSubtree[root]++;
            return;
        }
        last = index;
        index = reverseTree[index];
    }

}

void printTreeState(){
    printf("myIds: ");
    for(int i = 0; i < n; i++){
        printf("%d ", i);
    }

    printf("\nDepth: ");

    for(int i = 0; i < n; i++){
        printf("%d ", depth[i]);
    }

    printf("\nfpist: ");

    for(int i = 0; i < n; i++){
        printf("%d ", freePlacesInSubtree[i]);
    }
    printf("\n");
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie();

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

        //printTreeState();

    }


    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 281 ms 4160 KB Output is correct
3 Correct 263 ms 4404 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 17 ms 512 KB Output is correct
10 Correct 47 ms 1280 KB Output is correct
11 Correct 269 ms 4356 KB Output is correct
12 Correct 236 ms 4460 KB Output is correct
13 Correct 276 ms 4240 KB Output is correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 4224 KB Time limit exceeded
2 Execution timed out 1057 ms 13692 KB Time limit exceeded
3 Correct 213 ms 6388 KB Output is correct
4 Execution timed out 1065 ms 4712 KB Time limit exceeded
5 Execution timed out 1071 ms 4516 KB Time limit exceeded
6 Execution timed out 1062 ms 4472 KB Time limit exceeded
7 Execution timed out 1065 ms 3320 KB Time limit exceeded
8 Execution timed out 1078 ms 4248 KB Time limit exceeded
9 Execution timed out 1072 ms 13736 KB Time limit exceeded
10 Execution timed out 1062 ms 13816 KB Time limit exceeded
11 Execution timed out 1061 ms 13688 KB Time limit exceeded
12 Execution timed out 1069 ms 9720 KB Time limit exceeded
13 Execution timed out 1047 ms 19064 KB Time limit exceeded
14 Correct 252 ms 6388 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 7424 KB Time limit exceeded
2 Execution timed out 1064 ms 10236 KB Time limit exceeded
3 Execution timed out 1078 ms 17400 KB Time limit exceeded
4 Execution timed out 1070 ms 11000 KB Time limit exceeded
5 Execution timed out 1075 ms 11228 KB Time limit exceeded
6 Execution timed out 1072 ms 11132 KB Time limit exceeded
7 Execution timed out 1076 ms 8312 KB Time limit exceeded
8 Execution timed out 1064 ms 17396 KB Time limit exceeded
9 Execution timed out 1074 ms 13944 KB Time limit exceeded
10 Execution timed out 1058 ms 13880 KB Time limit exceeded
11 Execution timed out 1075 ms 13820 KB Time limit exceeded
12 Execution timed out 1064 ms 10108 KB Time limit exceeded
13 Execution timed out 1071 ms 21568 KB Time limit exceeded
14 Correct 258 ms 6388 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 13688 KB Time limit exceeded
2 Execution timed out 1076 ms 10232 KB Time limit exceeded
3 Execution timed out 1056 ms 21516 KB Time limit exceeded
4 Execution timed out 1073 ms 13688 KB Time limit exceeded
5 Execution timed out 1068 ms 13688 KB Time limit exceeded
6 Execution timed out 1067 ms 13688 KB Time limit exceeded
7 Execution timed out 1069 ms 9976 KB Time limit exceeded
8 Execution timed out 1070 ms 21568 KB Time limit exceeded
9 Correct 217 ms 6392 KB Output is correct