Submission #448064

#	Time	Username	Problem	Language	Result	Execution time	Memory
448064		Killer2501	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	462 ms	36412 KiB

ballmachine

#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define pii pair<ll, pll>
using namespace std;
using ll = int;
const int  N = 2e5+55;
const ll mod = 1e9+7;
const ll mod1 = 1e9+1;
const ll base = 311;
const ll base1 = 331;
ll m, n, t, k, a[N], tong, b[N], dp[N], c[N], lab[N], cnt, ans, P[N][20], h[N], d[N];
priority_queue< pll, vector<pll>, greater<pll> > pq;
string s[N];
vector<ll> adj[N];
vector<pll> e;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
bool cmp(const ll& x, const ll& y)
{
    return b[x] < b[y];
}
void dfs(ll u, ll p)
{
    for(int i = 1; i <= 18; i ++)P[u][i] = P[P[u][i-1]][i-1];
    b[u] = u;
    for(ll v : adj[u])
    {
        if(v == p)continue;
        P[v][0] = u;
        dfs(v, u);
        b[u] = min(b[u], b[v]);
    }
    if(p)
    {
        for(int i = 0; i < adj[u].size(); i ++)
        {
            if(adj[u][i] == p)
            {
                adj[u][i] = adj[u].back();
                adj[u].pop_back();
                break;
            }
        }
    }
    sort(adj[u].begin(), adj[u].end(), cmp);
}
void getid(ll u)
{
    for(ll v : adj[u])
    {
        //cout << u <<" "<<v<<'\n';
        h[v] = h[u] + 1;
        getid(v);
    }
    //cout << u <<" "<<h[u]<<'\n';
    d[u] = ++cnt;
}
ll par(ll u, ll dis)
{
    for(int i = 18; i >= 0; i --)if((dis >> i) & 1)u = P[u][i];
    return u;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        if(!a[i])k = i;
        else
        {
            adj[a[i]].pb(i);
            adj[i].pb(a[i]);
        }
    }
    //cout << k << '\n';
    dfs(k, 0);
    getid(k);
    for(int i = 1; i <= n; i ++)pq.push({d[i], i});
    while(m -- > 0)
    {
        ll x;
        cin >> t >> x;
        if(t == 1)
        {
            ans = 0;
            while(x -- > 0)
            {
                ans = pq.top().se;
                lab[ans] = 1;
                pq.pop();
            }
            cout << ans << '\n';
        }
        else
        {
            ll lf = 0, rt = h[x], mid;

            while(lf <= rt)
            {
                mid = (lf + rt) / 2;
                k = par(x, mid);
                if(lab[k])lf = mid + 1;
                else rt = mid - 1;
            }
            ans = par(x, rt);
            pq.push({d[ans], ans});
            lab[ans] = 0;
            //cout << ans << '\n';
            cout << h[x] - h[ans] << '\n';
        }
    }
}
/*
1
5 9
1 2 3 2
1 3 2 -2
2 2 3
1 3 2 -3
2 2 3
1 1 4 7
1 4 5 8
2 5 2
2 5 1
1 5 6
1 1 2 2
1 2 4 3
2 1 4
1 1 5 6
1 2 3 -2
2 3 5
*/

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs(ll, ll)':
ballmachine.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i = 0; i < adj[u].size(); i ++)
      |                        ~~^~~~~~~~~~~~~~~

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