제출 #336501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336501		Lecii	Ball Machine (BOI13_ballmachine)	C++14	29.90 / 100	1091 ms	30444 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,m;
int u,v;
vector<int> g[100005];
vector<pii> g2[100005];
int root;
int mi[100005];
bool a[100005];
int d[100005];
int pa[100005][18];
int las;

void dfs(int u,int dis)
{
    d[u]=dis;
    mi[u]=u;
    for(int i=0;i<g[u].size();i++)
    {
        pa[g[u][i]][0]=u;
        dfs(g[u][i],dis+1);
        mi[u]=min(mi[u],mi[g[u][i]]);
        g2[u].push_back({mi[g[u][i]],g[u][i]});
    }
    sort(g2[u].begin(),g2[u].end());
}
int dfs2(int u,int b)
{
    if(b<=0) return 0;
    for(int i=0;i<g2[u].size();i++)
    {
        if(!a[g2[u][i].second]) b=dfs2(g2[u][i].second,b);
        if(b<=0) return 0;
    }
    a[u]=1;
    las=u;
    --b;
    return b;
}
int main()
{
    ios_base::sync_with_stdio(false);
  	cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>u;
        if(u==0) root=i;
        else
            g[u].push_back(i);
    }
    pa[root][0]=root;
    dfs(root,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=17;j++) pa[i][j]=pa[pa[i][j-1]][j-1];

    while(m--)
    {
        cin>>u>>v;
        if(u==1)
        {
            dfs2(root,v);
            cout<<las<<endl;
        }
        else
        {
            int u=v;
            for(int i=17;i>=0;i--)
                if(a[pa[v][i]])
                    v=pa[v][i];
            a[v]=0;
            cout<<d[u]-d[v]<<endl;
        }
    }
    return 0;
}

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

ballmachine.cpp: In function 'void dfs(int, int)':
ballmachine.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<g[u].size();i++)
      |                 ~^~~~~~~~~~~~
ballmachine.cpp: In function 'int dfs2(int, int)':
ballmachine.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<g2[u].size();i++)
      |                 ~^~~~~~~~~~~~~

• Subtask 1: 5.769230769230769 / 25
• Subtask 2: 23.571428571428573 / 30
• Subtask 3: 0 / 40
• Subtask 4: 0.5555555555555556 / 5