이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
multiset <pair<int,int>>s;
const int N=1e5+10;
vector<int>v[N];
int n,q,lev[N],t[N],pa[N][25],yes[N];
void dfs (int x,int p)
{
pa[x][0]=p;
lev[x]=lev[p]+1;
for(int i=1;i<22;i++)
{
pa[x][i]=pa[pa[x][i-1]][i-1];
}
for(auto it:v[x])
{
if (it!=p)dfs(it,x);
}
t[x]=s.size();
s.insert({t[x],x});
}
void add (int x)
{
pair<int,int>last;
while (x--)
{
last=*s.begin();
yes[last.second]=1;
s.erase(s.begin());
}
cout<<last.second<<endl;
}
void del(int x)
{
int xx=x;
for(int i=22;i>-1;i--)
{
if (yes[pa[xx][i]]==1)
xx=pa[xx][i];
}
cout<<lev[x]-lev[xx]<<endl;
yes[xx]=0;
s.insert({t[xx],xx});
}
int main()
{
int x;
int root =0;
cin>>n>>q;
for(int i=1;i<n+1;i++)
{
cin>>x;
if (x==0)
{
root=i;
continue;
}
v[x].push_back(i);
}
for(int i=1;i<n;i++)
sort(v[i].begin(),v[i].end());
dfs (root,0);
while (q--)
{
cin>>x;
if (x==1)
{
cin>>x;
add(x);
}
else {
cin>>x;
del(x);
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |