Submission #785819

#	Time	Username	Problem	Language	Result	Execution time	Memory
785819		vjudge1	Ball Machine (BOI13_ballmachine)	C++17	25 / 100	1079 ms	32148 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

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

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

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

void depthFirstSearchB(const int& u)
{
    timeIn[u] = timer++;
    for (auto &v : adjList[u])
        depthFirstSearchB(u);
    timeOut[u] = timer++;
}

bool isAncestor(const int& u, const int& v)
{
    return timeIn[u] <= timeIn[v] && timeOut[v] <= timeOut[u];
}

bool queryTypeOne()
{
    int d = -1;
    for (int u = 1; u <= n; u++)
    {
        if (!adjList[u].empty() && adjList[u].size() != 2)
            return false;
        if (adjList[u].empty())
        {
            if (d == -1)
                d = depth[u];
            else if (d != depth[u])
                return false;
        }
    }
    return true;
}

bool queryTypeThree()
{
    if (queries[0].first != 1)
        return false;
    for (int i = 1; i < q; i++)
        if (queries[i].first != 2)
            return false;
    return true;
}

int manualInsert(const int& u)
{
    for (auto &v : adjList[u])
        if (!colour[v])
            return manualInsert(v);
    colour[u] = true;
    whiteNodes.insert({timeIn[u], u});
    return u;
}

int manualRemove(int u)
{
    int rollsCount = 0;
    while (u != root && colour[parent[u]])
        u = parent[u], rollsCount++;
    colour[u] = false;
    return rollsCount;
}

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);
    ancestor.resize(n + 1, vector<int>(20, -1));
    timeIn.resize(n + 1);
    timeOut.resize(n + 1);
    depthFirstSearchA(root);
    
    queries.resize(q);
    for (int i = 0; i < q; i++)
        cin >> queries[i].first >> queries[i].second;

    colour.resize(n + 1);

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

            if (type == 1)
            {
                int u;
                while (x --> 0)
                    u = manualInsert(root);
                cout << u << '\n';
            }

            if (type == 2)
                cout << manualRemove(x) << '\n';
        }

        return 0;
    }

    if (queryTypeThree())
    {
        for (int u = 1; u <= n; u++)
            whiteNodes.insert({timeIn[u], u});

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

            if (type == 1)
            {
                int u;
                while (x --> 0)
                {
                    u = manualInsert(root);
                    whiteNodes.erase({timeIn[u], u});
                }
                cout << u << '\n';
            }

            if (type == 2)
            {
                if (x == root || !colour[parent[x]])
                {
                    cout << 0 << '\n';
                    whiteNodes.insert({timeIn[x], x});
                    continue;
                }

                if (whiteNodes.empty())
                {
                    cout << depth[x] << '\n';
                    whiteNodes.insert({timeIn[root], root});
                    continue;
                }

                auto itr = whiteNodes.lower_bound({timeIn[x], x});
                int u = (--itr)->second;
                int v = x;
                for (int b = 19; b >= 0; b--)
                    if (ancestor[v][b] != -1)
                        if (depth[ancestor[v][b]] > depth[u])
                            v = ancestor[v][b];
                cout << depth[x] - depth[v] << '\n';
                whiteNodes.insert({timeIn[v], v});
            }
        }

        return 0;
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'void depthFirstSearchB(const int&)':
ballmachine.cpp:39:16: warning: unused variable 'v' [-Wunused-variable]
   39 |     for (auto &v : adjList[u])
      |                ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:166:30: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
  166 |                 cout << u << '\n';
      |                              ^~~~
ballmachine.cpp:139:30: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
  139 |                 cout << u << '\n';
      |                              ^~~~

• Subtask 1: 25 / 25
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40
• Subtask 4: 0 / 5