Submission #545520

#	Time	Username	Problem	Language	Result	Execution time	Memory
545520		shark25361	Ball Machine (BOI13_ballmachine)	C++14	47.70 / 100	1093 ms	12808 KiB

ballmachine

#include<bits/stdc++.h>
#include <iomanip>
using namespace std;

#define FIO ios_base::sync_with_stdio(false);cin.tie(0);
#define ll long long
#define for_t ll T;cin>>T;while(T--)
#define endl "\n"
#define mod 1000000007
#define inf 1000000000000000001
#define all(c) c.begin(),c.end()
#define pb push_back
#define lc(curr) (curr * 2)
#define rc(curr) ((curr * 2) + 1)

/*
    subtask 2: only elements whose parent does not have a ball can be removed
    update status of node with ball to false and ans = 0
*/

const int maxn = 100005;

vector<ll> adj[maxn];
ll parent[maxn];
vector<bool> hasball(maxn,false);
ll cnt;
ll root;
ll last;
ll minnode[maxn];//min node in the subtree of i

void roll(ll i)
{
    if(adj[i].size() == 0)
    {
        hasball[i] = true;
        cnt--;
        last = i;
        return;
    }
    for(auto it:adj[i])
    {
        if(cnt && !hasball[it])
        {
            roll(it);
        }
    }
    if(cnt && !hasball[i])
    {
        hasball[i] = true;
        cnt--;
        last = i;
    }
}

//find the contiguous nodes in ancestors of i that have a ball
void remnode(ll i)
{
    ll cnt = 0;
    ll curr = i;
    while(curr != root && hasball[parent[curr]])
    {
        curr = parent[curr];
        cnt++;
    }
    hasball[curr] = false;
    cout << cnt << endl;
}

bool comp(ll i,ll j)
{
    return minnode[i] < minnode[j];
}

void dfs(ll i)
{
    minnode[i] = i;
    for(auto it:adj[i])
    {
        dfs(it);
        minnode[i] = min(minnode[i],minnode[it]);
    }
}

void sol()
{
    ll n,q;
    cin >> n >> q;
    for(int i = 1;i <= n;i++)
    {
        cin >> parent[i];
        if(parent[i] == 0)
        {
            root = i;
        }
        else
        {
            adj[parent[i]].pb(i);
        }
    }
    dfs(root);
    for(int i = 1;i <= n;i++)
    {
        sort(all(adj[i]),comp);
    }
    /*
    cnt = 5;
    roll(1);
    for(int i = 1;i <= n;i++)
    {
        if(hasball[i])
        {
            cout << i << " has a ball." << endl;
        }
    }
    */
    for(int i = 0;i < q;i++)
    {
        ll x,y;
        cin >> x >> y;
        if(x == 1)
        {
            cnt = y;
            roll(root);
            cout << last << endl;
        }
        else
        {
            remnode(y);
        }
    }
}

int main()
{
    FIO
    sol();
}

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