제출 #203204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
203204		mdn2002	Ball Machine (BOI13_ballmachine)	C++14	39.07 / 100	1096 ms	61916 KiB

ballmachine

#include<bits/stdc++.h>
using namespace std;
int n,m,rt,st[100500],fn[100500],tim=1,mn[100500],on[100500],spt[100500][30],dp[100500];
vector<int>gr[100500];
set<pair<int,int> >s;
void dfs(int x)
{
    mn[x]=x;
    for(int i=0; i<gr[x].size(); i++)
    {
        int u=gr[x][i];
        dfs(u);
        mn[x]=min(mn[x],mn[u]);
    }
}
void dfs1(int x,int p)
{
    spt[x][0]=p;
    dp[x]=dp[p]+1;
    st[x]=tim++;
    vector<pair<int,int> >v;
    for(int i=0; i<gr[x].size(); i++)
    {
        int u=gr[x][i];
        v.push_back({mn[u],u});
    }
    sort(v.begin(),v.end());
    for(int i=gr[x].size()-1; i>=0; i--)
    {
        int u=v[i].second;
        dfs1(u,x);
    }
    fn[x]=tim;
}
bool ck(int x,int mid)
{
    int dif=mid;
    if(dif>dp[x])return 0;
    for(int i=0; i<=21; i++)
    {
        if((dif&(1<<i)))x=spt[x][i];
    }
    if(on[x]==0)return 0;
    else return 1;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        int x;
        cin>>x;
        if(x==0)
        {
            rt=i;
            continue;
        }
        gr[x].push_back(i);
    }
    dfs(rt);
    dfs1(rt,0);
    for(int i=1; i<=n; i++)s.insert({st[i],i});
    for(int i=1; i<=25; i++)
    {
        for(int j=1; j<=n; j++)spt[j][i]=spt[spt[j][i-1]][i-1];
    }
    while(m--)
    {
        int t,x;
        cin>>t>>x;
        if(t==1)
        {
            int to;
            while(x--)
            {
                pair<int,int>z=*--s.end();
                s.erase(--s.end());
                to=z.second;
                on[to]++;
            }
            cout<<to<<endl;
        }
        else
        {
            int l=0,r=n,mid;
            while(l<r)
            {
                mid=(l+r)/2;
                if(ck(x,mid))l=mid+1;
                else r=mid;
            }
            cout<<l-1<<endl;
            int dif=l-1;
            for(int i=0; i<=21; i++)
            {
                if((dif&(1<<i)))x=spt[x][i];
            }
            on[x]=0;
        }
    }
}

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

ballmachine.cpp: In function 'void dfs(int)':
ballmachine.cpp:9:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gr[x].size(); i++)
                  ~^~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs1(int, int)':
ballmachine.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gr[x].size(); i++)
                  ~^~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:81:19: warning: 'to' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout<<to<<endl;
                   ^~

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