Submission #623575

#	Time	Username	Problem	Language	Result	Execution time	Memory
623575		Hanksburger	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	176 ms	23340 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
int par[100005][17], mn[100005], t[100005], tt;
vector<int> child[100005];
set<pair<int, int> > s;
bool ball[100005];
bool cmp(int u, int v)
{
    return mn[u]<mn[v];
}
void dfs(int u)
{
    mn[u]=u;
    for (int v:child[u])
    {
        dfs(v);
        mn[u]=min(mn[u], mn[v]);
    }
}
void dfs2(int u)
{
    sort(child[u].begin(), child[u].end(), cmp);
    for (int v:child[u])
        dfs2(v);
    t[u]=++tt;
//    cout << "t[" << u << "]=" << t[u] << '\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q, r;
    cin >> n >> q;
    for (int i=1; i<=n; i++)
    {
        cin >> par[i][0];
        child[par[i][0]].push_back(i);
        if (!par[i][0])
            r=i;
    }
    for (int i=1; i<=16; i++)
        for (int j=1; j<=n; j++)
            par[j][i]=par[par[j][i-1]][i-1];
    dfs(r);
    dfs2(r);
    for (int i=1; i<=n; i++)
        s.insert({t[i], i});
    for (int i=1; i<=q; i++)
    {
        int x, y;
        cin >> x >> y;
        if (x==1)
        {
            for (int j=1; j<=y; j++)
            {
                int u=s.begin()->second;
                s.erase({t[u], u});
                ball[u]=1;
//                cout << "set ball[" << u << "] to 1\n";
                if (j==y)
                    cout << u << '\n';
            }
        }
        else
        {
            int cnt=0;
            for (int j=16; j>=0; j--)
            {
                if (ball[par[y][j]])
                {
                    y=par[y][j];
                    cnt+=1<<j;
                }
            }
            s.insert({t[y], y});
            ball[y]=0;
//            cout << "set ball[" << y << "] to 0\n";
            cout << cnt << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:46:9: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |     dfs2(r);
      |     ~~~~^~~

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