Submission #545522

#	Time	Username	Problem	Language	Result	Execution time	Memory
545522		shark25361	Ball Machine (BOI13_ballmachine)	C++14	4.78 / 100	1099 ms	31956 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)

const int maxn = 100005;

vector<ll> adj[maxn];
ll parent[maxn];
vector<bool> hasball(maxn,false);
ll cnt,root,last;
ll minnode[maxn];//min node in the subtree of i
vector<ll> order;
map<ll,ll> mp;
set<pair<ll,ll>> nb;//these nodes do not have balls

//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 dfs2(ll i)
{
    for(auto it:adj[i])
    {
        dfs2(it);
        order.pb(it);
    }
    order.pb(i);
    mp[i] = order.size() - 1;
    nb.insert({mp[i],i});
}

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);
    }
    dfs2(root);
    for(int i = 0;i < q;i++)
    {
        ll x,y;
        cin >> x >> y;
        if(x == 1)
        {
            for(int j = 0;j < y;j++)
            {
                ll u = (*nb.begin()).second;
                hasball[u] = true;
                last = u;
                nb.erase(*nb.begin());
            }
            cout << last << endl;
        }
        else
        {
            remnode(y);
        }
    }
}

int main()
{
    FIO
    sol();
}

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