oj.uz

Submission #518310

# Submission time Handle Problem Language Result Execution time Memory
518310 2022-01-23T11:00:22 Z athensclub Ball Machine (BOI13_ballmachine) C++14
77.4359 / 100
 388 ms 27008 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> 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
        {
            orderToFill.push(nodeToOrder[k]);
            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];
                }
                else
                {
                    temp--;
                }
            }
            hasBall[target] = false;
            cout << (depth[k] - depth[target]) << endl;
        }
    }
}

Compilation message

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

Subtask #1
5.76923076923 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 288 KB Output isn't correct
2 Incorrect 249 ms 12336 KB Output isn't correct
3 Correct 239 ms 12316 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Correct 2 ms 332 KB Output is correct
7 Incorrect 4 ms 428 KB Output isn't correct
8 Incorrect 4 ms 460 KB Output isn't correct
9 Incorrect 18 ms 972 KB Output isn't correct
10 Incorrect 49 ms 3252 KB Output isn't correct
11 Incorrect 251 ms 11816 KB Output isn't correct
12 Correct 213 ms 11856 KB Output is correct
13 Incorrect 230 ms 12160 KB Output isn't correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 5828 KB Output is correct
2 Correct 361 ms 21836 KB Output is correct
3 Correct 222 ms 17468 KB Output is correct
4 Correct 180 ms 7336 KB Output is correct
5 Correct 169 ms 7160 KB Output is correct
6 Correct 164 ms 7064 KB Output is correct
7 Correct 168 ms 6184 KB Output is correct
8 Correct 142 ms 5888 KB Output is correct
9 Correct 346 ms 22440 KB Output is correct
10 Correct 353 ms 21824 KB Output is correct
11 Correct 321 ms 21536 KB Output is correct
12 Correct 376 ms 19396 KB Output is correct
13 Correct 318 ms 23804 KB Output is correct
14 Correct 248 ms 17076 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 11740 KB Output is correct
2 Correct 347 ms 20332 KB Output is correct
3 Correct 247 ms 22004 KB Output is correct
4 Correct 228 ms 18228 KB Output is correct
5 Correct 214 ms 17808 KB Output is correct
6 Correct 238 ms 17856 KB Output is correct
7 Correct 246 ms 16264 KB Output is correct
8 Correct 248 ms 21780 KB Output is correct
9 Correct 358 ms 22480 KB Output is correct
10 Correct 363 ms 21984 KB Output is correct
11 Correct 349 ms 21932 KB Output is correct
12 Correct 326 ms 19876 KB Output is correct
13 Correct 388 ms 27008 KB Output is correct
14 Correct 256 ms 17212 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 380 ms 21932 KB Output isn't correct
2 Incorrect 342 ms 19780 KB Output isn't correct
3 Correct 349 ms 26268 KB Output is correct
4 Incorrect 366 ms 21980 KB Output isn't correct
5 Incorrect 360 ms 21496 KB Output isn't correct
6 Incorrect 374 ms 21028 KB Output isn't correct
7 Incorrect 312 ms 19780 KB Output isn't correct
8 Correct 300 ms 26248 KB Output is correct
9 Correct 221 ms 16584 KB Output is correct