Submission #621299

#	Time	Username	Problem	Language	Result	Execution time	Memory
621299		353cerega	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	424 ms	46360 KiB

ballmachine

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>


using namespace std;


using ll = long long;
using ld = long double;

#define X first
#define Y second

//const ll mod = 1000000007;
const ll mod = 998244353;

vector<vector<ll>> g, up;
vector<ll> mn;
ll K = 20;

void dfs0(ll u)
{
    mn[u] = u;
    for (ll j=1;j<K;j++)
    {
        up[u][j] = up[up[u][j-1]][j-1];
    }
    for (ll v: g[u])
    {
        dfs0(v);
        mn[u] = min(mn[u],mn[v]);
    }
}

vector<ll> Q;

void dfs(ll u)
{
    vector<pair<ll,ll>> ord;
    for (ll v: g[u])
    {
        ord.push_back({mn[v],v});
    }
    sort(ord.begin(),ord.end());
    for (auto x: ord) dfs(x.Y);
    Q.push_back(u);
}

void solve()
{
    ll n, q;
    cin >> n >> q;
    g.resize(n+1);
    mn.resize(n+1);
    up.resize(n+1,vector<ll>(K));
    for (ll i=1;i<=n;i++)
    {
        ll x;
        cin >> x;
        up[i][0] = x;
        g[x].push_back(i);
    }
    dfs0(0);
    dfs(0);
    vector<ll> Q2(n+1);
    for (ll i=0;i<=n;i++) Q2[Q[i]] = i;
    set<ll> kek;
    for (ll i=0;i<=n;i++) kek.insert(i);
    vector<ll> was(n+1);
    while (q--)
    {
        ll t;
        ll x;
        cin >> t >> x;
        if (t==1)
        {
            ll L = 0;
            while (x--)
            {
                L = *kek.begin();
                kek.erase(L);
                was[Q[L]] = 1;
            }
            cout << Q[L] << "\n";
            continue;
        }
        ll A = 0;
        for (ll j=K-1;j>=0;j--)
        {
            if (was[up[x][j]]==1)
            {
                A += (1LL<<j);
                x = up[x][j];
            }
        }
        cout << A << "\n";
        was[x] = 0;
        kek.insert(Q2[x]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    ll T;
    T = 1;
    //cin >> T;
    while (T--) solve();
}

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