Submission #106442

# Submission time Handle Problem Language Result Execution time Memory
106442 2019-04-18T13:42:11 Z RedNextCentury Ball Machine (BOI13_ballmachine) C++14
100 / 100
608 ms 46044 KB
#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;
        }
    }
}
# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 387 ms 34188 KB Output is correct
3 Correct 239 ms 34296 KB Output is correct
4 Correct 23 ms 23808 KB Output is correct
5 Correct 30 ms 23936 KB Output is correct
6 Correct 24 ms 23936 KB Output is correct
7 Correct 26 ms 24064 KB Output is correct
8 Correct 29 ms 24056 KB Output is correct
9 Correct 38 ms 24448 KB Output is correct
10 Correct 86 ms 26360 KB Output is correct
11 Correct 360 ms 34176 KB Output is correct
12 Correct 301 ms 34296 KB Output is correct
13 Correct 355 ms 34236 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 208 ms 28136 KB Output is correct
2 Correct 448 ms 42056 KB Output is correct
3 Correct 303 ms 39028 KB Output is correct
4 Correct 265 ms 29704 KB Output is correct
5 Correct 228 ms 29432 KB Output is correct
6 Correct 226 ms 29432 KB Output is correct
7 Correct 252 ms 28792 KB Output is correct
8 Correct 168 ms 28124 KB Output is correct
9 Correct 463 ms 42872 KB Output is correct
10 Correct 450 ms 42104 KB Output is correct
11 Correct 445 ms 42256 KB Output is correct
12 Correct 497 ms 40572 KB Output is correct
13 Correct 410 ms 43268 KB Output is correct
14 Correct 306 ms 39184 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 231 ms 33400 KB Output is correct
2 Correct 554 ms 41388 KB Output is correct
3 Correct 403 ms 41592 KB Output is correct
4 Correct 335 ms 39060 KB Output is correct
5 Correct 411 ms 38492 KB Output is correct
6 Correct 377 ms 38692 KB Output is correct
7 Correct 355 ms 37624 KB Output is correct
8 Correct 398 ms 41592 KB Output is correct
9 Correct 608 ms 42748 KB Output is correct
10 Correct 526 ms 42360 KB Output is correct
11 Correct 543 ms 42532 KB Output is correct
12 Correct 555 ms 41212 KB Output is correct
13 Correct 513 ms 46044 KB Output is correct
14 Correct 474 ms 39308 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 462 ms 42872 KB Output is correct
2 Correct 478 ms 41180 KB Output is correct
3 Correct 397 ms 45820 KB Output is correct
4 Correct 548 ms 42876 KB Output is correct
5 Correct 526 ms 42348 KB Output is correct
6 Correct 411 ms 42232 KB Output is correct
7 Correct 575 ms 41252 KB Output is correct
8 Correct 391 ms 45828 KB Output is correct
9 Correct 308 ms 39148 KB Output is correct