oj.uz

Submission #238451

# Submission time Handle Problem Language Result Execution time Memory
238451 2020-06-11T11:41:41 Z Andrei_Cotor Ball Machine (BOI13_ballmachine) C++11
100 / 100
 336 ms 26232 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>

using namespace std;

int P[20][100005];
vector<int> Sons[100005];
int Val[100005];
bool Ball[100005];
int Priority[100005];
set<pair<int,int> > S;

void dfs(int nod)
{
    Val[nod]=nod;
    for(auto son:Sons[nod])
    {
        dfs(son);
        Val[nod]=min(Val[nod],Val[son]);
    }
}

bool cmp(int a, int b)
{
    return Val[a]<Val[b];
}

int nr;
void getPriority(int nod)
{
    sort(Sons[nod].begin(),Sons[nod].end(),cmp);
    for(auto son:Sons[nod])
        getPriority(son);

    Priority[nod]=++nr;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,q;
    cin>>n>>q;

    int root=0;
    for(int i=1; i<=n; i++)
    {
        cin>>P[0][i];
        Sons[P[0][i]].push_back(i);

        if(P[0][i]==0)
            root=i;
    }

    for(int i=1; i<=16; i++)
    {
        for(int j=1; j<=n; j++)
            P[i][j]=P[i-1][P[i-1][j]];
    }

    dfs(root);
    getPriority(root);

    for(int i=1; i<=n; i++)
        S.insert({Priority[i],i});

    for(int i=1; i<=q; i++)
    {
        int tip,x;
        cin>>tip>>x;

        if(tip==1)
        {
            int rez=0;
            for(int j=1; j<=x; j++) //suma x-ilor va fi max n+q
            {
                int nod=(*S.begin()).second;
                S.erase(S.begin());
                Ball[nod]=1;
                rez=nod;
            }
            cout<<rez<<"\n";
        }
        else
        {
            int rez=0;
            for(int i=16; i>=0; i--)
            {
                if(Ball[P[i][x]])
                {
                    rez+=(1<<i);
                    x=P[i][x];
                }
            }

            cout<<rez<<"\n";

            Ball[x]=0;
            S.insert({Priority[x],x});
        }
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 147 ms 13176 KB Output is correct
3 Correct 82 ms 13176 KB Output is correct
4 Correct 7 ms 2816 KB Output is correct
5 Correct 6 ms 2848 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 7 ms 2944 KB Output is correct
8 Correct 7 ms 2944 KB Output is correct
9 Correct 12 ms 3456 KB Output is correct
10 Correct 27 ms 5368 KB Output is correct
11 Correct 194 ms 13176 KB Output is correct
12 Correct 99 ms 13180 KB Output is correct
13 Correct 118 ms 13176 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7544 KB Output is correct
2 Correct 259 ms 21624 KB Output is correct
3 Correct 98 ms 17396 KB Output is correct
4 Correct 108 ms 8952 KB Output is correct
5 Correct 118 ms 8824 KB Output is correct
6 Correct 68 ms 8824 KB Output is correct
7 Correct 79 ms 8044 KB Output is correct
8 Correct 39 ms 7544 KB Output is correct
9 Correct 235 ms 22008 KB Output is correct
10 Correct 252 ms 21496 KB Output is correct
11 Correct 154 ms 21496 KB Output is correct
12 Correct 190 ms 19616 KB Output is correct
13 Correct 134 ms 23264 KB Output is correct
14 Correct 126 ms 17396 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 12408 KB Output is correct
2 Correct 227 ms 20088 KB Output is correct
3 Correct 154 ms 21328 KB Output is correct
4 Correct 147 ms 18168 KB Output is correct
5 Correct 146 ms 17784 KB Output is correct
6 Correct 139 ms 17784 KB Output is correct
7 Correct 144 ms 16504 KB Output is correct
8 Correct 142 ms 21368 KB Output is correct
9 Correct 227 ms 22392 KB Output is correct
10 Correct 336 ms 21752 KB Output is correct
11 Correct 217 ms 21752 KB Output is correct
12 Correct 228 ms 20216 KB Output is correct
13 Correct 228 ms 26232 KB Output is correct
14 Correct 178 ms 17908 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 22392 KB Output is correct
2 Correct 227 ms 20216 KB Output is correct
3 Correct 128 ms 25848 KB Output is correct
4 Correct 228 ms 22428 KB Output is correct
5 Correct 216 ms 21752 KB Output is correct
6 Correct 182 ms 21880 KB Output is correct
7 Correct 292 ms 20216 KB Output is correct
8 Correct 127 ms 25848 KB Output is correct
9 Correct 93 ms 17396 KB Output is correct