oj.uz

Submission #102315

# Submission time Handle Problem Language Result Execution time Memory
102315 2019-03-24T09:59:15 Z TomGautot Ball Machine (BOI13_ballmachine) C++14
32.6984 / 100
 1000 ms 21504 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()
{
    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 2 ms 384 KB Output is correct
2 Correct 327 ms 4216 KB Output is correct
3 Correct 341 ms 4344 KB Output is correct
4 Correct 2 ms 256 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 4 ms 384 KB Output is correct
9 Correct 20 ms 632 KB Output is correct
10 Correct 56 ms 1280 KB Output is correct
11 Correct 309 ms 4216 KB Output is correct
12 Correct 287 ms 4364 KB Output is correct
13 Correct 292 ms 4220 KB Output is correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 4268 KB Time limit exceeded
2 Execution timed out 1071 ms 13688 KB Time limit exceeded
3 Correct 283 ms 6388 KB Output is correct
4 Execution timed out 1065 ms 4600 KB Time limit exceeded
5 Execution timed out 1068 ms 4472 KB Time limit exceeded
6 Execution timed out 1075 ms 4528 KB Time limit exceeded
7 Execution timed out 1067 ms 3200 KB Time limit exceeded
8 Execution timed out 1073 ms 4256 KB Time limit exceeded
9 Execution timed out 1055 ms 13688 KB Time limit exceeded
10 Execution timed out 1069 ms 13688 KB Time limit exceeded
11 Execution timed out 1067 ms 13688 KB Time limit exceeded
12 Execution timed out 1065 ms 9848 KB Time limit exceeded
13 Execution timed out 1068 ms 18988 KB Time limit exceeded
14 Correct 248 ms 6432 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 7392 KB Time limit exceeded
2 Execution timed out 1075 ms 10008 KB Time limit exceeded
3 Execution timed out 1043 ms 17292 KB Time limit exceeded
4 Execution timed out 1025 ms 11096 KB Time limit exceeded
5 Execution timed out 1045 ms 11216 KB Time limit exceeded
6 Execution timed out 1062 ms 11100 KB Time limit exceeded
7 Execution timed out 1060 ms 8312 KB Time limit exceeded
8 Execution timed out 1047 ms 17348 KB Time limit exceeded
9 Execution timed out 1055 ms 13940 KB Time limit exceeded
10 Execution timed out 1077 ms 13944 KB Time limit exceeded
11 Execution timed out 1039 ms 13772 KB Time limit exceeded
12 Execution timed out 1061 ms 10104 KB Time limit exceeded
13 Execution timed out 1084 ms 21504 KB Time limit exceeded
14 Correct 316 ms 6388 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 13708 KB Time limit exceeded
2 Execution timed out 1081 ms 10104 KB Time limit exceeded
3 Execution timed out 1054 ms 21384 KB Time limit exceeded
4 Execution timed out 1072 ms 13816 KB Time limit exceeded
5 Execution timed out 1074 ms 13816 KB Time limit exceeded
6 Execution timed out 1077 ms 13684 KB Time limit exceeded
7 Execution timed out 1068 ms 10232 KB Time limit exceeded
8 Execution timed out 1039 ms 21496 KB Time limit exceeded
9 Correct 292 ms 6388 KB Output is correct