oj.uz

Submission #159675

# Submission time Handle Problem Language Result Execution time Memory
159675 2019-10-23T21:21:46 Z Rouge_Hugo Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 1000 ms 28344 KB 
#include <bits/stdc++.h>

using namespace std;
set <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);
        }
    }
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2808 KB Output isn't correct
2 Execution timed out 1069 ms 14180 KB Time limit exceeded
3 Incorrect 447 ms 14612 KB Output isn't correct
4 Execution timed out 1077 ms 2680 KB Time limit exceeded
5 Incorrect 5 ms 2680 KB Output isn't correct
6 Incorrect 7 ms 2936 KB Output isn't correct
7 Execution timed out 1076 ms 2808 KB Time limit exceeded
8 Execution timed out 1075 ms 2936 KB Time limit exceeded
9 Incorrect 39 ms 3448 KB Output isn't correct
10 Execution timed out 1076 ms 5496 KB Time limit exceeded
11 Incorrect 529 ms 14200 KB Output isn't correct
12 Incorrect 438 ms 14572 KB Output isn't correct
13 Incorrect 490 ms 14176 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 7732 KB Output is correct
2 Incorrect 611 ms 23772 KB Output isn't correct
3 Incorrect 454 ms 20092 KB Output isn't correct
4 Execution timed out 1089 ms 9080 KB Time limit exceeded
5 Execution timed out 1082 ms 8952 KB Time limit exceeded
6 Incorrect 379 ms 9340 KB Output isn't correct
7 Incorrect 405 ms 8184 KB Output isn't correct
8 Correct 300 ms 7544 KB Output is correct
9 Incorrect 598 ms 24064 KB Output isn't correct
10 Incorrect 608 ms 23928 KB Output isn't correct
11 Incorrect 564 ms 23656 KB Output isn't correct
12 Incorrect 599 ms 21772 KB Output isn't correct
13 Correct 485 ms 24960 KB Output is correct
14 Incorrect 455 ms 19956 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 297 ms 13592 KB Output isn't correct
2 Incorrect 653 ms 22252 KB Output isn't correct
3 Correct 394 ms 23084 KB Output is correct
4 Incorrect 384 ms 19832 KB Output isn't correct
5 Incorrect 393 ms 19604 KB Output isn't correct
6 Incorrect 400 ms 19448 KB Output isn't correct
7 Incorrect 395 ms 18396 KB Output isn't correct
8 Correct 437 ms 23072 KB Output is correct
9 Incorrect 610 ms 24316 KB Output isn't correct
10 Incorrect 650 ms 24004 KB Output isn't correct
11 Incorrect 639 ms 23800 KB Output isn't correct
12 Incorrect 635 ms 22264 KB Output isn't correct
13 Correct 636 ms 28344 KB Output is correct
14 Incorrect 615 ms 19956 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 605 ms 24192 KB Output isn't correct
2 Incorrect 646 ms 22400 KB Output isn't correct
3 Correct 504 ms 27772 KB Output is correct
4 Incorrect 592 ms 24280 KB Output isn't correct
5 Incorrect 722 ms 23952 KB Output isn't correct
6 Incorrect 564 ms 23672 KB Output isn't correct
7 Incorrect 609 ms 22136 KB Output isn't correct
8 Correct 497 ms 27924 KB Output is correct
9 Incorrect 451 ms 19956 KB Output isn't correct