oj.uz

Submission #518284

# Submission time Handle Problem Language Result Execution time Memory
518284 2022-01-23T10:17:41 Z athensclub Ball Machine (BOI13_ballmachine) C++14
0 / 100
 1000 ms 28568 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;

int findMinSubtree(int node, vector<int> children[], int minSubtree[])
{
    if (minSubtree[node] > 0)
        return minSubtree[node];

    int temp = node;
    for (int child : children[node])
        temp = min(temp, findMinSubtree(child, children, minSubtree));

    minSubtree[node] = temp;
    return temp;
}

void visitOrdered(int node, vector<int> children[], vector<int> &order)
{
    for (int child : children[node])
        visitOrdered(child, children, order);

    order.push_back(node);
}

void findUp(int node, vector<int> children[], int parent[], vector<vector<int>> &up, int logN, int depth[])
{
    up[node][0] = parent[node] == 0 ? node : parent[node];
    for (int i = 1; i <= logN; i++)
        up[node][i] = up[up[node][i - 1]][i - 1];

    for (int child : children[node])
    {
        depth[child] = depth[node] + 1;
        findUp(child, children, parent, up, logN, depth);
    }
}

int main()
{
    int n, q;
    cin >> n >> q;

    int parent[n + 5];
    int minSubtree[n + 5];
    bool hasBall[n + 5];
    vector<int> children[n + 5];
    int root;
    for (int i = 1; i <= n; i++)
    {
        hasBall[i] = false;
        minSubtree[i] = 0;
        cin >> parent[i];
        if (parent[i] == 0)
            root = i;
        else
            children[parent[i]].push_back(i);
    }

    findMinSubtree(root, children, minSubtree);
    for (int i = 1; i <= n; i++)
    {
        sort(children[i].begin(), children[i].end(), [&minSubtree](const int node1, const int node2)
             { return minSubtree[node1] < minSubtree[node2]; });
    }

    int logN = (int)ceil(log2(n));
    int depth[n + 5];
    depth[root] = 0;
    vector<vector<int>> up(n + 5, vector<int>(logN + 1));
    findUp(root, children, parent, up, logN, depth);

    vector<int> order(n + 5);
    visitOrdered(root, children, order);

    for (int i = 0; i < q; i++)
    {
        int t, k;
        cin >> t >> k;
        if (t == 1)
        {
            for (int i = 0; i < k; i++)
                hasBall[order[i]] = true;
        }
        else
        {
            int temp = logN;
            int tempNode = k;
            int target = k;
            while (i >= 0)
            {
                if (hasBall[up[tempNode][i]])
                {
                    target = up[tempNode][i];
                    tempNode = up[tempNode][i];
                }
                else
                {
                    i--;
                }
            }

            hasBall[target] = false;
            if (target != k)
                hasBall[target] = true;
            cout << (depth[k] - depth[target]) << endl;
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:90:17: warning: unused variable 'temp' [-Wunused-variable]
   90 |             int temp = logN;
      |                 ^~~~
ballmachine.cpp:77:17: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |     visitOrdered(root, children, order);
      |     ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 1992 KB Time limit exceeded
2 Execution timed out 1050 ms 13656 KB Time limit exceeded
3 Incorrect 141 ms 11832 KB Output isn't correct
4 Execution timed out 1072 ms 2088 KB Time limit exceeded
5 Execution timed out 1084 ms 2120 KB Time limit exceeded
6 Execution timed out 1089 ms 2132 KB Time limit exceeded
7 Execution timed out 1014 ms 2084 KB Time limit exceeded
8 Execution timed out 1082 ms 2240 KB Time limit exceeded
9 Execution timed out 1047 ms 2648 KB Time limit exceeded
10 Execution timed out 1076 ms 4884 KB Time limit exceeded
11 Execution timed out 1076 ms 13524 KB Time limit exceeded
12 Incorrect 143 ms 11812 KB Output isn't correct
13 Execution timed out 1082 ms 13672 KB Time limit exceeded

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 7192 KB Time limit exceeded
2 Execution timed out 1096 ms 23548 KB Time limit exceeded
3 Execution timed out 1058 ms 18688 KB Time limit exceeded
4 Execution timed out 1067 ms 9160 KB Time limit exceeded
5 Execution timed out 1050 ms 8800 KB Time limit exceeded
6 Execution timed out 1071 ms 8988 KB Time limit exceeded
7 Execution timed out 1012 ms 7568 KB Time limit exceeded
8 Execution timed out 1060 ms 7192 KB Time limit exceeded
9 Execution timed out 1083 ms 24016 KB Time limit exceeded
10 Execution timed out 1075 ms 23560 KB Time limit exceeded
11 Execution timed out 1088 ms 23412 KB Time limit exceeded
12 Execution timed out 1086 ms 21420 KB Time limit exceeded
13 Execution timed out 1031 ms 25380 KB Time limit exceeded
14 Execution timed out 1062 ms 18812 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 12972 KB Time limit exceeded
2 Execution timed out 1097 ms 21732 KB Time limit exceeded
3 Execution timed out 1061 ms 23208 KB Time limit exceeded
4 Execution timed out 1054 ms 19396 KB Time limit exceeded
5 Execution timed out 1031 ms 19228 KB Time limit exceeded
6 Execution timed out 1081 ms 19084 KB Time limit exceeded
7 Execution timed out 1025 ms 17576 KB Time limit exceeded
8 Execution timed out 1062 ms 23112 KB Time limit exceeded
9 Execution timed out 1031 ms 23900 KB Time limit exceeded
10 Execution timed out 1050 ms 23628 KB Time limit exceeded
11 Execution timed out 1044 ms 23476 KB Time limit exceeded
12 Execution timed out 1040 ms 21624 KB Time limit exceeded
13 Execution timed out 1044 ms 28568 KB Time limit exceeded
14 Execution timed out 1077 ms 19132 KB Time limit exceeded

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 23980 KB Time limit exceeded
2 Execution timed out 1086 ms 21648 KB Time limit exceeded
3 Execution timed out 1032 ms 28312 KB Time limit exceeded
4 Execution timed out 1055 ms 24056 KB Time limit exceeded
5 Execution timed out 1006 ms 23548 KB Time limit exceeded
6 Execution timed out 1068 ms 23456 KB Time limit exceeded
7 Execution timed out 1081 ms 21604 KB Time limit exceeded
8 Execution timed out 1078 ms 28432 KB Time limit exceeded
9 Execution timed out 1079 ms 18920 KB Time limit exceeded