Submission #639883

#	Time	Username	Problem	Language	Result	Execution time	Memory
639883		pls33	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	283 ms	31948 KiB

ballmachine

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;

using pf32 = pair<float, float>;
using pf64 = pair<double, double>;
using pf80 = pair<long double, long double>;
using vf32 = vector<float>;
using vf64 = vector<double>;
using vf80 = vector<long double>;
using vpf32 = vector<pf32>;
using vpf64 = vector<pf64>;
using vpf80 = vector<pf80>;
using vvf32 = vector<vf32>;
using vvf64 = vector<vf64>;
using vvf80 = vector<vf80>;
using vvpf32 = vector<vpf32>;
using vvpf64 = vector<vpf64>;
using vvpf80 = vector<vpf80>;

template <typename key, typename val>
using ord_map = tree<key, val, less<key>, rb_tree_tag,
                     tree_order_statistics_node_update>;

template <typename key>
using ord_set = tree<key, null_type, less<key>, rb_tree_tag,
                     tree_order_statistics_node_update>;

const int BUF_SZ = 1 << 15;
inline namespace fast_in
{
    char buf[BUF_SZ];
    int pos;
    int len;

    char next_char(FILE *f)
    {
        if (pos == len)
        {
            pos = 0;
            len = (int)fread(buf, 1, BUF_SZ, f);

            if (!len)
            {
                return EOF;
            }
        }

        return buf[pos++];
    }

    int read_int(FILE *f)
    {
        int x;
        char ch;
        int sgn = 1;

        while (!isdigit(ch = next_char(f)))
        {
            if (ch == '-')
            {
                sgn *= -1;
            }
        }

        x = ch - '0';
        while (isdigit(ch = next_char(f)))
        {
            x = x * 10 + (ch - '0');
        }

        return x * sgn;
    }
}

/**
 * @brief gale programos flush_out kviest!!
 */
inline namespace fast_out
{
    char buf[BUF_SZ];
    int pos;

    void flush_out(FILE *f)
    {
        fwrite(buf, 1, pos, f);
        pos = 0;
    }

    void write_char(char c, FILE *f)
    {
        if (pos == BUF_SZ)
        {
            flush_out(f);
        }

        buf[pos++] = c;
    }

    void write_int(int x, FILE *f)
    {
        static char num_buf[100];

        if (x < 0)
        {
            write_char('-', f);
            x *= -1;
        }

        int len = 0;
        for (; x >= 10; x /= 10)
        {
            num_buf[len++] = (char)('0' + (x % 10));
        }

        write_char((char)('0' + x), f);
        while (len)
        {
            write_char(num_buf[--len], f);
        }
        write_char('\n', f);
    }
}
#pragma endregion

using filled_t = bitset<(size_t)1e5>;

void find_min(int node, vvi32 &adj, vi32 &sub_min)
{
    int cur = node;
    for (int i = 1; i < adj[node].size(); i++)
    {
        int next = adj[node][i];

        find_min(next, adj, sub_min);

        cur = min(cur, sub_min[next]);
    }

    sub_min[node] = cur;
}

void sort_adj(vvi32 &adj, vi32 &sub_min)
{
    auto comp = [&sub_min](int a, int b)
    {
        return sub_min[a] < sub_min[b];
    };

    for (int i = 0; i < adj.size(); i++)
    {
        auto &next = adj[i];
        sort(next.begin() + 1, next.end(), comp);
    }
}

void find_order(int node, vvi32 &adj, vi32 &order, int &count)
{
    for (int i = 1; i < adj[node].size(); i++)
    {
        find_order(adj[node][i], adj, order, count);
    }

    order[node] = count;
    count++;
}

void find_up(vvi32 &up, vvi32 &adj)
{
    for (size_t i = 0; i < adj.size(); i++)
    {
        up[i][0] = adj[i][0];
    }

    for (size_t power = 1; power < up[0].size(); power++)
    {
        for (size_t i = 0; i < adj.size(); i++)
        {
            if (up[i][power - 1] == -1)
            {
                continue;
            }

            up[i][power] = up[up[i][power - 1]][power - 1];
        }
    }
}

p32 first_filled(int node, int root, vvi32 &up, filled_t &filled)
{
    if (node == root)
    {
        return {node, 0};
    }

    int anc = node;
    int last = up[0].size() - 1;
    int distance = 0;
    for (int i = last; i >= 0; i--)
    {
        int cur = up[anc][i];

        if (cur != -1 && filled[cur])
        {
            anc = cur;
            distance += 1 << i;
        }
    }

    return {anc, distance};
}

p32 remove(int node, int root, vvi32 &up, filled_t &filled)
{
    p32 res = first_filled(node, root, up, filled);
    filled[res.first] = false;
    return res;
}

int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("ball_machine.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
    freopen("con", "r", stdin);
    system("pause"); });
#endif
#endif

    int n, q;
    cin >> n >> q;

    vvi32 adj(n);
    int root = 0;

    for (size_t i = 0; i < n; i++)
    {
        int parent;
        cin >> parent;

        parent--;

        adj[i].insert(adj[i].begin(), parent);
        if (parent != -1)
        {
            adj[parent].push_back(i);
        }
        else
        {
            root = i;
        }
    }

    vi32 sub_min(n);
    filled_t filled;
    find_min(root, adj, sub_min);
    sort_adj(adj, sub_min);

    vvi32 up(n, vi32(int(log2(n) + 1), -1));
    vi32 order(n);
    int count = 0;

    find_up(up, adj);
    find_order(root, adj, order, count);

    auto comp = [order](int a, int b)
    {
        return order[a] < order[b];
    };
    set<int, decltype(comp)> empty(comp);
    for (size_t i = 0; i < n; i++)
    {
        empty.insert(i);
    }

    for (size_t query = 0; query < q; query++)
    {
        int type, node;
        cin >> type >> node;

        if (type == 1)
        {
            int last = -1;
            auto it = empty.begin();
            for (int i = 0; i < node; i++)
            {
                last = *it;
                filled[last] = true;
                it++;
            }

            empty.erase(empty.begin(), it);
            cout << last + 1 << '\n';
        }
        else
        {
            node--;

            p32 res = remove(node, root, up, filled);
            empty.insert(res.first);

            cout << res.second << '\n';
        }
    }

    return 0;
}

Compilation message (stderr)

ballmachine.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
ballmachine.cpp:151: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
  151 | #pragma endregion
      | 
ballmachine.cpp: In function 'void find_min(int, vvi32&, vi32&)':
ballmachine.cpp:158:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for (int i = 1; i < adj[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void sort_adj(vvi32&, vi32&)':
ballmachine.cpp:177:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for (int i = 0; i < adj.size(); i++)
      |                     ~~^~~~~~~~~~~~
ballmachine.cpp: In function 'void find_order(int, vvi32&, vi32&, int&)':
ballmachine.cpp:186:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for (int i = 1; i < adj[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:268:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  268 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~
ballmachine.cpp:303:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  303 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~
ballmachine.cpp:308:34: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  308 |     for (size_t query = 0; query < q; query++)
      |                            ~~~~~~^~~

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