oj.uz

Submission #159676

# Submission time Handle Problem Language Result Execution time Memory
159676 2019-10-23T21:22:49 Z Rouge_Hugo Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 1000 ms 28280 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()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    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 1073 ms 14408 KB Time limit exceeded
3 Incorrect 367 ms 14352 KB Output isn't correct
4 Execution timed out 1072 ms 2680 KB Time limit exceeded
5 Incorrect 5 ms 2808 KB Output isn't correct
6 Incorrect 7 ms 2936 KB Output isn't correct
7 Execution timed out 1078 ms 2940 KB Time limit exceeded
8 Execution timed out 1081 ms 2936 KB Time limit exceeded
9 Incorrect 33 ms 3448 KB Output isn't correct
10 Execution timed out 1081 ms 5624 KB Time limit exceeded
11 Incorrect 500 ms 14268 KB Output isn't correct
12 Incorrect 373 ms 14368 KB Output isn't correct
13 Incorrect 415 ms 14200 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 7520 KB Output is correct
2 Incorrect 554 ms 23732 KB Output isn't correct
3 Incorrect 384 ms 20004 KB Output isn't correct
4 Execution timed out 1080 ms 9080 KB Time limit exceeded
5 Execution timed out 1074 ms 8952 KB Time limit exceeded
6 Incorrect 335 ms 9208 KB Output isn't correct
7 Incorrect 330 ms 8312 KB Output isn't correct
8 Correct 259 ms 7480 KB Output is correct
9 Incorrect 519 ms 24172 KB Output isn't correct
10 Incorrect 565 ms 24056 KB Output isn't correct
11 Incorrect 496 ms 23644 KB Output isn't correct
12 Incorrect 562 ms 21880 KB Output isn't correct
13 Correct 398 ms 24824 KB Output is correct
14 Incorrect 389 ms 20104 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 239 ms 13436 KB Output isn't correct
2 Incorrect 512 ms 22412 KB Output isn't correct
3 Correct 319 ms 23160 KB Output is correct
4 Incorrect 349 ms 19704 KB Output isn't correct
5 Incorrect 356 ms 19508 KB Output isn't correct
6 Incorrect 323 ms 19484 KB Output isn't correct
7 Incorrect 338 ms 18436 KB Output isn't correct
8 Correct 318 ms 23032 KB Output is correct
9 Incorrect 570 ms 24480 KB Output isn't correct
10 Incorrect 525 ms 23800 KB Output isn't correct
11 Incorrect 516 ms 23908 KB Output isn't correct
12 Incorrect 517 ms 22268 KB Output isn't correct
13 Correct 500 ms 28280 KB Output is correct
14 Incorrect 465 ms 20100 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 496 ms 24184 KB Output isn't correct
2 Incorrect 518 ms 22196 KB Output isn't correct
3 Correct 412 ms 27804 KB Output is correct
4 Incorrect 517 ms 24276 KB Output isn't correct
5 Incorrect 518 ms 23928 KB Output isn't correct
6 Incorrect 497 ms 23672 KB Output isn't correct
7 Incorrect 519 ms 22264 KB Output isn't correct
8 Correct 407 ms 27768 KB Output is correct
9 Incorrect 372 ms 20088 KB Output isn't correct