제출 #63353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63353		Bodo171	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	838 ms	68356 KiB

ballmachine

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int nmax=100005;
vector<int> v[nmax];
int mn[nmax],r[nmax],wh[nmax],aib[nmax],negru[nmax],lev[nmax];
int tt[17][nmax];
int nr,n,q,i,j,x,R,type,poz,orig;
bool comp(int unu,int doi)
{
    return (mn[unu]<mn[doi]);
}
void dfs1(int x)
{
    for(int i=0;i<v[x].size();i++)
        {
            lev[v[x][i]]=lev[x]+1;
            dfs1(v[x][i]);
        }
    sort(v[x].begin(),v[x].end(),comp);
    mn[x]=x;
    if(v[x].size()) mn[x]=min(mn[x],mn[v[x][0]]);
}
void dfs2(int x)
{
    for(int i=0;i<v[x].size();i++)
        dfs2(v[x][i]);
    r[++nr]=x;wh[x]=nr;
}
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,int val)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
        aib[idx]+=val;
}
int get_poz()
{
    int ret=0;
    for(int p=16;p>=0;p--)
        if(ret+(1<<p)<=n&&aib[ret+(1<<p)]==(1<<p))
           ret+=(1<<p);
    ret++;
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>q;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        tt[0][i]=x;
        if(x)v[x].push_back(i);
        else R=i;
    }
    for(i=1;i<=16;i++)
        for(j=1;j<=n;j++)
          tt[i][j]=tt[i-1][tt[i-1][j]];
    dfs1(R);
    dfs2(R);
    for(i=1;i<=q;i++)
    {
        cin>>type>>x;
        if(type==1)
        {
            for(j=1;j<=x;j++)
            {
                poz=get_poz();
                update(poz,1);
                negru[r[poz]]=1;
            }
            cout<<r[poz]<<'\n';
        }
        else
        {
            orig=x;
            for(int p=16;p>=0;p--)
                if(negru[tt[p][x]])
                   x=tt[p][x];
            update(wh[x],-1);
            negru[x]=0;
            cout<<lev[orig]-lev[x]<<'\n';
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

ballmachine.cpp: In function 'void dfs1(int)':
ballmachine.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs2(int)':
ballmachine.cpp:28:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~

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