oj.uz

Submission #159673

# Submission time Handle Problem Language Result Execution time Memory
159673 2019-10-23T21:12:42 Z Rouge_Hugo Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 712 ms 29944 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)
{
    int last;

    while (x--)
    {
       auto l=s.begin();
         last=(*l).second;
        yes[last]=1;
        s.erase(s.begin());
    }
    cout<<last<<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);
        }
    }
}

Compilation message

ballmachine.cpp: In function 'void add(int)':
ballmachine.cpp:34:11: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<last<<endl;
           ^~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2936 KB Output isn't correct
2 Incorrect 537 ms 15480 KB Output isn't correct
3 Incorrect 462 ms 15340 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 7 ms 2936 KB Output isn't correct
7 Incorrect 8 ms 2808 KB Output isn't correct
8 Incorrect 9 ms 2936 KB Output isn't correct
9 Incorrect 39 ms 3448 KB Output isn't correct
10 Incorrect 104 ms 5752 KB Output isn't correct
11 Incorrect 565 ms 15448 KB Output isn't correct
12 Incorrect 448 ms 15352 KB Output isn't correct
13 Incorrect 549 ms 15308 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 8096 KB Output is correct
2 Incorrect 592 ms 24952 KB Output isn't correct
3 Incorrect 481 ms 20904 KB Output isn't correct
4 Incorrect 398 ms 9976 KB Output isn't correct
5 Incorrect 401 ms 9800 KB Output isn't correct
6 Incorrect 396 ms 9848 KB Output isn't correct
7 Incorrect 377 ms 8952 KB Output isn't correct
8 Correct 301 ms 7964 KB Output is correct
9 Incorrect 611 ms 25364 KB Output isn't correct
10 Incorrect 638 ms 25148 KB Output isn't correct
11 Incorrect 574 ms 24984 KB Output isn't correct
12 Incorrect 594 ms 23024 KB Output isn't correct
13 Correct 483 ms 25976 KB Output is correct
14 Incorrect 486 ms 20908 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 14072 KB Output isn't correct
2 Incorrect 712 ms 23508 KB Output isn't correct
3 Correct 410 ms 24116 KB Output is correct
4 Incorrect 386 ms 20728 KB Output isn't correct
5 Incorrect 396 ms 20480 KB Output isn't correct
6 Incorrect 399 ms 20364 KB Output isn't correct
7 Incorrect 384 ms 19192 KB Output isn't correct
8 Correct 397 ms 23960 KB Output is correct
9 Incorrect 619 ms 25764 KB Output isn't correct
10 Incorrect 634 ms 25180 KB Output isn't correct
11 Incorrect 655 ms 25156 KB Output isn't correct
12 Incorrect 643 ms 23800 KB Output isn't correct
13 Correct 632 ms 29944 KB Output is correct
14 Incorrect 559 ms 21236 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 641 ms 25636 KB Output isn't correct
2 Incorrect 645 ms 23544 KB Output isn't correct
3 Correct 511 ms 28920 KB Output is correct
4 Incorrect 605 ms 25544 KB Output isn't correct
5 Incorrect 620 ms 25212 KB Output isn't correct
6 Incorrect 588 ms 24952 KB Output isn't correct
7 Incorrect 606 ms 23516 KB Output isn't correct
8 Correct 509 ms 29048 KB Output is correct
9 Incorrect 466 ms 20852 KB Output isn't correct