Submission #92137

#	Time	Username	Problem	Language	Result	Execution time	Memory
92137		luckyboy	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	318 ms	21496 KiB

ballmachine

/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 100005
#define maxm 1000006
#define pii pair <int,int>
#define Task ""
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int n,q,t[maxn << 2],lz[maxn << 2],cnt,out[maxn],pos[maxn],mi[maxn],root,par[maxn][17];
vector <int> a[maxn];
bool comp(int x,int y)
{
    return mi[x] < mi[y];
}
void Pre_Dfs(int u)
{
    mi[u] = u;
    for (int v : a[u])
    {
        Pre_Dfs(v);
        mi[u] = min(mi[u],mi[v]);
    }
}
void Dfs(int u)
{
    for (int v : a[u])
    {
        par[v][0] = u;
        FOR(i,1,16)
            par[v][i] = par[par[v][i-1]][i-1];
        Dfs(v);
    }
    out[u] = ++cnt;
    pos[cnt] = u;
}
int Find(int l,int r,int id,int remain)
{
    if (l == r) return l;
    int mid = (l+r) >> 1;
    if (mid - l + 1 - t[2*id] >= remain) return Find(l,mid,2*id,remain);
    return Find(mid+1,r,2*id+1,remain - (mid - l + 1 - t[2*id]));
}
void Push(int l,int r,int id)
{
    if (lz[id] != -1)
    {
        int mid = (l+r) >> 1;
        lz[2*id] = lz[2*id+1] = lz[id];
        t[2*id] = (mid - l + 1) * lz[id];
        t[2*id+1] = (r - mid) * lz[id];
        lz[id] = -1;
    }
}
void Update(int l,int r,int id,int u,int v,int val)
{
    if (l > v || r < u) return;
    if (u <= l && r <= v)
    {
        t[id] = (r - l + 1) * val;
        lz[id] = val;
        return;
    }
    Push(l,r,id);
    int mid = (l+r) >> 1;
    Update(l,mid,2*id,u,v,val);
    Update(mid+1,r,2*id+1,u,v,val);
    t[id] = t[2*id+1] + t[2*id];
}
int Get(int l,int r,int id,int x)
{
    if (l == r) return t[id];
    Push(l,r,id);
    int mid = (l+r) >> 1;
    if (mid >= x) return Get(l,mid,2*id,x);
    return Get(mid+1,r,2*id+1,x);
}
int main()
{
    ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    //freopen(Task".inp", "r",stdin);
    //freopen(Task".out", "w",stdout);
    cin >> n >> q;
    FOR(i,1,n << 2) lz[i] = -1;
    FOR(i,1,n)
    {
        int x;
        cin >> x;
        if (!x) root = i;
        else a[x].pb(i);
    }
    Pre_Dfs(root);
    FOR(i,1,n) sort(a[i].begin(),a[i].end(),comp);
    Dfs(root);
    while (q--)
    {
        int type,x;
        cin >> type >> x;
        if (type & 1)
        {
            int ww = Find(1,n,1,x);
            cout << pos[ww] << '\n';
            Update(1,n,1,1,ww,1);
        }
        else
        {
            int ans = 0;
            FORD(i,16,0)
            {
                int nex = par[x][i];
                if (!nex || !Get(1,n,1,out[nex])) continue;
                ans += 1 << i;
                x = nex;
            }
            Update(1,n,1,out[x],out[x],0);
            cout << ans << '\n';
        }
    }
    return 0;
}

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