oj.uz

Submission #786944

# Submission time Handle Problem Language Result Execution time Memory
786944 2023-07-18T15:21:23 Z n1427 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 189 ms 27932 KB 
#include <bits/stdc++.h>

using namespace std;

int n, q, root, timer = 0;
vector<int> parent, depth, subtreeMin, subtreeSize, timeIn;
vector<vector<int>> ancestor;
vector<vector<int>> adjList;
vector<pair<int, int>> queries;

vector<bool> colour;
priority_queue<pair<int, int>> whiteNodes;

void depthFirstSearchA(const int& u)
{
    subtreeMin[u] = u;
    subtreeSize[u] = 1;
    
    for (auto &v : adjList[u])
    {
        depth[v] = depth[u] + 1;
        ancestor[v][0] = u;
        for (int b = 1; ancestor[v][b - 1] != -1; b++)
            ancestor[v][b] = ancestor[ancestor[v][b - 1]][b - 1];
        depthFirstSearchA(v);
        subtreeMin[u] = min(subtreeMin[v], subtreeMin[u]);
        subtreeSize[u] += subtreeSize[v];
    }
    
    sort(adjList[u].begin(), adjList[u].end(), [&](const int& v1, const int& v2) -> bool
    {
        return subtreeMin[v1] < subtreeMin[v2];
    });
}

void depthFirstSearchB(const int& u)
{
    timeIn[u] = timer++;
    whiteNodes.push({timeIn[u], u});
    for (auto itr = adjList[u].rbegin(); itr != adjList[u].rend(); itr++)
        depthFirstSearchB(*itr);
}

int main()
{
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);

    ios::sync_with_stdio(false);

    cin >> n >> q;
    adjList.resize(n + 1);
    parent.resize(n + 1);
    for (int u = 1; u <= n; u++)
    {
        cin >> parent[u];
        if (parent[u] == 0)
            root = u;
        else
            adjList[parent[u]].push_back(u);
    }

    depth.resize(n + 1);
    subtreeMin.resize(n + 1);
    subtreeSize.resize(n + 1);
    timeIn.resize(n + 1);
    ancestor.resize(n + 1, vector<int>(20, -1));
    depthFirstSearchA(root);
    depthFirstSearchB(root);
    
    queries.resize(q);
    for (int i = 0; i < q; i++)
        cin >> queries[i].first >> queries[i].second;

    colour.resize(n + 1);

    for (auto &query : queries)
    {
        int type = query.first, x = query.second;

        if (type == 1)
        {
            int u = -1;
            while (x --> 0)
            {
                u = whiteNodes.top().second;
                whiteNodes.pop();
                colour[u] = true;
            }
            cout << u << '\n';
        }

        if (type == 2)
        {
            int v = x;
            for (int b = 19; b >= 0; b--)
                if (ancestor[v][b] != -1)
                    if (colour[ancestor[v][b]])
                        v = ancestor[v][b];

            cout << depth[x] - depth[v] << '\n';
            colour[v] = false;
            whiteNodes.push({timeIn[v], v});
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 70 ms 13416 KB Output is correct
3 Correct 54 ms 13692 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 5 ms 1108 KB Output is correct
10 Correct 12 ms 3620 KB Output is correct
11 Correct 59 ms 13484 KB Output is correct
12 Correct 43 ms 13680 KB Output is correct
13 Correct 67 ms 13452 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6124 KB Output is correct
2 Correct 126 ms 23276 KB Output is correct
3 Correct 54 ms 19520 KB Output is correct
4 Correct 39 ms 7848 KB Output is correct
5 Correct 43 ms 7768 KB Output is correct
6 Correct 45 ms 7776 KB Output is correct
7 Correct 40 ms 6840 KB Output is correct
8 Correct 27 ms 6080 KB Output is correct
9 Correct 120 ms 23760 KB Output is correct
10 Correct 127 ms 23212 KB Output is correct
11 Correct 115 ms 23232 KB Output is correct
12 Correct 135 ms 21216 KB Output is correct
13 Correct 94 ms 24788 KB Output is correct
14 Correct 68 ms 19588 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 12088 KB Output is correct
2 Correct 136 ms 21840 KB Output is correct
3 Correct 98 ms 22068 KB Output is correct
4 Correct 74 ms 18888 KB Output is correct
5 Correct 101 ms 18564 KB Output is correct
6 Correct 85 ms 18576 KB Output is correct
7 Correct 95 ms 17272 KB Output is correct
8 Correct 99 ms 22000 KB Output is correct
9 Correct 119 ms 23876 KB Output is correct
10 Correct 155 ms 23420 KB Output is correct
11 Correct 189 ms 23480 KB Output is correct
12 Correct 122 ms 21852 KB Output is correct
13 Correct 178 ms 27932 KB Output is correct
14 Correct 71 ms 19688 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 24040 KB Output is correct
2 Correct 139 ms 21932 KB Output is correct
3 Correct 119 ms 27844 KB Output is correct
4 Correct 122 ms 24048 KB Output is correct
5 Correct 131 ms 23488 KB Output is correct
6 Correct 140 ms 23444 KB Output is correct
7 Correct 128 ms 21928 KB Output is correct
8 Correct 114 ms 27780 KB Output is correct
9 Correct 57 ms 19648 KB Output is correct