oj.uz

Submission #159674

# Submission time Handle Problem Language Result Execution time Memory
159674 2019-10-23T21:20:17 Z Rouge_Hugo Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 648 ms 28380 KB 
#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);
        }
    }
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2680 KB Output isn't correct
2 Incorrect 514 ms 14176 KB Output isn't correct
3 Incorrect 499 ms 14584 KB Output isn't correct
4 Incorrect 4 ms 2680 KB Output isn't correct
5 Incorrect 5 ms 2808 KB Output isn't correct
6 Incorrect 6 ms 2808 KB Output isn't correct
7 Incorrect 8 ms 2808 KB Output isn't correct
8 Incorrect 10 ms 2808 KB Output isn't correct
9 Incorrect 40 ms 3440 KB Output isn't correct
10 Incorrect 107 ms 5768 KB Output isn't correct
11 Incorrect 565 ms 14172 KB Output isn't correct
12 Incorrect 442 ms 14472 KB Output isn't correct
13 Incorrect 539 ms 14280 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 7556 KB Output is correct
2 Incorrect 597 ms 23628 KB Output isn't correct
3 Incorrect 462 ms 20040 KB Output isn't correct
4 Incorrect 369 ms 9208 KB Output isn't correct
5 Incorrect 395 ms 9248 KB Output isn't correct
6 Incorrect 376 ms 9052 KB Output isn't correct
7 Incorrect 380 ms 8220 KB Output isn't correct
8 Correct 304 ms 7480 KB Output is correct
9 Incorrect 622 ms 24036 KB Output isn't correct
10 Incorrect 591 ms 23684 KB Output isn't correct
11 Incorrect 569 ms 23544 KB Output isn't correct
12 Incorrect 587 ms 21716 KB Output isn't correct
13 Correct 483 ms 24824 KB Output is correct
14 Incorrect 464 ms 20036 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 285 ms 13432 KB Output isn't correct
2 Incorrect 617 ms 22332 KB Output isn't correct
3 Correct 394 ms 23104 KB Output is correct
4 Incorrect 385 ms 19960 KB Output isn't correct
5 Incorrect 388 ms 19452 KB Output isn't correct
6 Incorrect 403 ms 19660 KB Output isn't correct
7 Incorrect 438 ms 18268 KB Output isn't correct
8 Correct 439 ms 23160 KB Output is correct
9 Incorrect 630 ms 24284 KB Output isn't correct
10 Incorrect 632 ms 23772 KB Output isn't correct
11 Incorrect 640 ms 23828 KB Output isn't correct
12 Incorrect 629 ms 22264 KB Output isn't correct
13 Correct 640 ms 28380 KB Output is correct
14 Incorrect 585 ms 19960 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 610 ms 24088 KB Output isn't correct
2 Incorrect 638 ms 22392 KB Output isn't correct
3 Correct 503 ms 27640 KB Output is correct
4 Incorrect 617 ms 24224 KB Output isn't correct
5 Incorrect 623 ms 23800 KB Output isn't correct
6 Incorrect 580 ms 23692 KB Output isn't correct
7 Incorrect 648 ms 22264 KB Output isn't correct
8 Correct 502 ms 27864 KB Output is correct
9 Incorrect 462 ms 19956 KB Output isn't correct