oj.uz

Submission #518289

# Submission time Handle Problem Language Result Execution time Memory
518289 2022-01-23T10:31:31 Z athensclub Ball Machine (BOI13_ballmachine) C++14
61.9963 / 100
 388 ms 26044 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;
    visitOrdered(root, children, order);

    for (int i = 0; i < q; i++)
    {
        int t, k;
        cin >> t >> k;
        if (t == 1)
        {
            for (int j = 0; j < k; j++)
                hasBall[order[j]] = true;
            cout << order[k-1] << endl;
        }
        else
        {
            int temp = logN;
            int tempNode = k;
            int target = k;
            while (temp >= 0 && target != root)
            {
                if (hasBall[up[tempNode][temp]])
                {
                //cout << temp << " " << tempNode << endl;
                    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:94:40: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |             while (temp >= 0 && target != root)
      |                                 ~~~~~~~^~~~~~~

Subtask #1
9.61538461538 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Correct 235 ms 10908 KB Output is correct
3 Correct 209 ms 11136 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 3 ms 332 KB Output isn't correct
8 Correct 4 ms 332 KB Output is correct
9 Incorrect 19 ms 888 KB Output isn't correct
10 Incorrect 43 ms 2948 KB Output isn't correct
11 Incorrect 226 ms 11028 KB Output isn't correct
12 Correct 201 ms 11108 KB Output is correct
13 Incorrect 226 ms 10920 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 5276 KB Output is correct
2 Incorrect 317 ms 20764 KB Output isn't correct
3 Correct 220 ms 16172 KB Output is correct
4 Incorrect 153 ms 6720 KB Output isn't correct
5 Incorrect 158 ms 6500 KB Output isn't correct
6 Incorrect 199 ms 6468 KB Output isn't correct
7 Incorrect 153 ms 5448 KB Output isn't correct
8 Correct 161 ms 5208 KB Output is correct
9 Incorrect 269 ms 21028 KB Output isn't correct
10 Incorrect 310 ms 20616 KB Output isn't correct
11 Incorrect 288 ms 20680 KB Output isn't correct
12 Incorrect 334 ms 18260 KB Output isn't correct
13 Correct 269 ms 22916 KB Output is correct
14 Correct 226 ms 16224 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 10752 KB Output is correct
2 Correct 386 ms 18776 KB Output is correct
3 Correct 232 ms 20956 KB Output is correct
4 Correct 237 ms 17024 KB Output is correct
5 Correct 195 ms 16724 KB Output is correct
6 Correct 199 ms 16640 KB Output is correct
7 Correct 227 ms 15196 KB Output is correct
8 Correct 225 ms 20772 KB Output is correct
9 Correct 341 ms 21216 KB Output is correct
10 Correct 355 ms 20776 KB Output is correct
11 Correct 355 ms 20836 KB Output is correct
12 Correct 316 ms 18900 KB Output is correct
13 Correct 388 ms 26044 KB Output is correct
14 Correct 304 ms 16252 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 339 ms 21344 KB Output isn't correct
2 Incorrect 311 ms 18936 KB Output isn't correct
3 Correct 292 ms 26036 KB Output is correct
4 Incorrect 305 ms 21276 KB Output isn't correct
5 Incorrect 301 ms 20836 KB Output isn't correct
6 Incorrect 318 ms 20688 KB Output isn't correct
7 Incorrect 320 ms 18748 KB Output isn't correct
8 Correct 297 ms 25896 KB Output is correct
9 Correct 206 ms 16404 KB Output is correct