oj.uz

Submission #519137

# Submission time Handle Problem Language Result Execution time Memory
519137 2022-01-25T18:02:54 Z athensclub Ball Machine (BOI13_ballmachine) C++14
100 / 100
 289 ms 26944 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()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    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> orderToNode, nodeToOrder(n + 5);
    visitOrdered(root, children, orderToNode);
    for (int i = 0; i < orderToNode.size(); i++)
        nodeToOrder[orderToNode[i]] = i;

    int r = 0;
    priority_queue<int, vector<int>, greater<int>> orderToFill;
    for (int i = 0; i < q; i++)
    {
        int t, k;
        cin >> t >> k;
        if (t == 1)
        {
            int lastFilled = -1;
            while (k > 0 && !orderToFill.empty())
            {
                hasBall[orderToNode[orderToFill.top()]] = true;
                lastFilled = orderToNode[orderToFill.top()];
                orderToFill.pop();
                k--;
            }

            if (k == 0)
            {
                cout << lastFilled << endl;
            }
            else
            {
                for (int j = 0; j < k; j++)
                    hasBall[orderToNode[r + j]] = true;
                r += k;
                cout << orderToNode[r - 1] << endl;
            }
        }
        else
        {
            int temp = logN;
            int tempNode = k;
            int target = k;
            while (temp >= 0 && target != root)
            {
                if (hasBall[up[tempNode][temp]])
                {
                    target = up[tempNode][temp];
                    tempNode = up[tempNode][temp];
                }
                temp--;
            }
            hasBall[target] = false;
            orderToFill.push(nodeToOrder[target]);
            cout << (depth[k] - depth[target]) << endl;
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i = 0; i < orderToNode.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:117:40: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  117 |             while (temp >= 0 && target != root)
      |                                 ~~~~~~~^~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 192 ms 11280 KB Output is correct
3 Correct 163 ms 11408 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 15 ms 972 KB Output is correct
10 Correct 46 ms 3020 KB Output is correct
11 Correct 183 ms 11428 KB Output is correct
12 Correct 173 ms 11348 KB Output is correct
13 Correct 181 ms 11332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 5268 KB Output is correct
2 Correct 261 ms 21492 KB Output is correct
3 Correct 190 ms 16572 KB Output is correct
4 Correct 134 ms 6932 KB Output is correct
5 Correct 157 ms 6768 KB Output is correct
6 Correct 129 ms 6632 KB Output is correct
7 Correct 132 ms 5676 KB Output is correct
8 Correct 113 ms 5364 KB Output is correct
9 Correct 240 ms 21744 KB Output is correct
10 Correct 251 ms 21376 KB Output is correct
11 Correct 228 ms 21020 KB Output is correct
12 Correct 251 ms 19000 KB Output is correct
13 Correct 227 ms 23364 KB Output is correct
14 Correct 174 ms 16544 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 11220 KB Output is correct
2 Correct 285 ms 19900 KB Output is correct
3 Correct 186 ms 21532 KB Output is correct
4 Correct 159 ms 17656 KB Output is correct
5 Correct 165 ms 17380 KB Output is correct
6 Correct 172 ms 17272 KB Output is correct
7 Correct 206 ms 15728 KB Output is correct
8 Correct 191 ms 21564 KB Output is correct
9 Correct 244 ms 22080 KB Output is correct
10 Correct 269 ms 21764 KB Output is correct
11 Correct 268 ms 21736 KB Output is correct
12 Correct 282 ms 19812 KB Output is correct
13 Correct 289 ms 26944 KB Output is correct
14 Correct 199 ms 17212 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 22204 KB Output is correct
2 Correct 273 ms 19904 KB Output is correct
3 Correct 230 ms 26336 KB Output is correct
4 Correct 287 ms 22088 KB Output is correct
5 Correct 285 ms 21508 KB Output is correct
6 Correct 251 ms 21120 KB Output is correct
7 Correct 279 ms 19804 KB Output is correct
8 Correct 224 ms 26336 KB Output is correct
9 Correct 190 ms 16636 KB Output is correct