# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
106441 | RedNextCentury | Ball Machine (BOI13_ballmachine) | C++14 | 520 ms | 47456 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1000000];
int mn[1000000];
bool cmp(int a,int b)
{
return mn[a]<mn[b];
}
void pre(int v)
{
mn[v]=v;
for (auto u:adj[v])
{
pre(u);
mn[v]=min(mn[v],mn[u]);
}
}
int pa[1000001][21];
int ord[1000001];
int tt=1;
void dfs(int v)
{
for (auto u:adj[v])
dfs(u);
ord[v]=tt++;
}
bool has[1000000];
int main()
{
freopen("out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,q;
cin>>n>>q;
int root=-1;
for (int i=1;i<=n;i++)
{
cin>>pa[i][0];
if (pa[i][0]==0) root = i;
else adj[pa[i][0]].push_back(i);
}
for (int j=1;j<=18;j++)
for (int i=1;i<=n;i++)
pa[i][j]=pa[pa[i][j-1]][j-1];
pre(root);
for (int i=1;i<=n;i++)
sort(adj[i].begin(),adj[i].end(),cmp);
dfs(root);
set<pair<int,int> > s;
for (int i=1;i<=n;i++)
s.insert({ord[i],i});
while(q--)
{
int t,v;
cin>>t>>v;
if (t==1)
{
pair<int,int> p;
while(v--)
{
p = *s.begin();
s.erase(s.begin());
has[p.second]=1;
}
cout<<p.second<<endl;
}
else
{
int u = v;
int ret=0;
for (int i=18;i>=0;i--)
if (has[pa[u][i]])
u = pa[u][i] , ret+=(1<<i);
has[u]=0;
s.insert({ord[u],u});
cout<<ret<<endl;
}
}
}
Compilation message (stderr)
# | 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... |