oj.uz

Submission #884640

# Submission time Handle Problem Language Result Execution time Memory
884640 2023-12-07T20:51:44 Z AndreiBOTO Ball Machine (BOI13_ballmachine) C++14
100 / 100
 143 ms 79408 KB 
#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

const int NMAX=5e5+5;

priority_queue<pair<int,int> , vector<pair<int,int>>, greater<pair<int,int>>>pq;
vector<int>v[NMAX];
int asc[25][NMAX];
bool viz[NMAX];
int dp[NMAX];
int ti[NMAX];
int to[NMAX];
int kon;

bool cmp(int x,int y)
{
    return dp[x]<dp[y];
}

void dfs1(int p,int tata)
{
    dp[p]=p;
    for(int i=1;i<=24;i++)
        asc[i][p]=asc[i-1][asc[i-1][p]];
    for(auto i:v[p])
    {
        if(i!=tata)
        {
            asc[0][i]=p;
            dfs1(i,p);
            dp[p]=min(dp[p],dp[i]);
        }
    }
}

void dfs2(int p,int tata)
{
    sort(v[p].begin(),v[p].end(),cmp);
    for(auto i:v[p])
    {
        if(i!=tata)
            dfs2(i,p);
    }
    to[p]=++kon;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,q,i,j,root=-1;
    cin>>n>>q;
    for(i=1;i<=n;i++)
    {
        int x,y;
        cin>>x;
        if(x==0)
            root=i;
        else
        {
            v[x].push_back(i);
            v[i].push_back(x);
        }
    }
    dfs1(root,0);
    dfs2(root,0);
    for(i=1;i<=n;i++)
        pq.push(make_pair(to[i],i));
    while(q--)
    {
        int type,x;
        cin>>type>>x;
        if(type==1)
        {
            int best=-1;
            for(i=1;i<=x;i++)
            {
                int p=pq.top().second;
                pq.pop();
                best=p;
                viz[p]=true;
            }
            cout<<best<<"\n";
        }
        else
        {
            int kon=0;
            int p=x;
            for(int e=24;e>=0;e--)
                if(viz[asc[e][p]])
                {
                    kon+=(1<<e);
                    p=asc[e][p];
                }
            viz[p]=false;
            pq.push(make_pair(to[p],p));
            cout<<kon<<"\n";
        }
    }
    return 0;
}

Compilation message

ballmachine.cpp:3: warning: ignoring '#pragma optimize GCC' [-Wunknown-pragmas]
    3 | #pragma optimize GCC ("Ofast")
      | 
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:65:15: warning: unused variable 'y' [-Wunused-variable]
   65 |         int x,y;
      |               ^
ballmachine.cpp:61:15: warning: unused variable 'j' [-Wunused-variable]
   61 |     int n,q,i,j,root=-1;
      |               ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 63212 KB Output is correct
2 Correct 72 ms 69576 KB Output is correct
3 Correct 51 ms 69580 KB Output is correct
4 Correct 8 ms 63068 KB Output is correct
5 Correct 9 ms 63208 KB Output is correct
6 Correct 9 ms 63068 KB Output is correct
7 Correct 9 ms 63064 KB Output is correct
8 Correct 9 ms 63064 KB Output is correct
9 Correct 12 ms 63324 KB Output is correct
10 Correct 21 ms 64376 KB Output is correct
11 Correct 72 ms 69656 KB Output is correct
12 Correct 53 ms 69788 KB Output is correct
13 Correct 69 ms 69580 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 66252 KB Output is correct
2 Correct 110 ms 75212 KB Output is correct
3 Correct 83 ms 71228 KB Output is correct
4 Correct 46 ms 66768 KB Output is correct
5 Correct 46 ms 66784 KB Output is correct
6 Correct 46 ms 66956 KB Output is correct
7 Correct 50 ms 65972 KB Output is correct
8 Correct 33 ms 66616 KB Output is correct
9 Correct 97 ms 75324 KB Output is correct
10 Correct 134 ms 75328 KB Output is correct
11 Correct 93 ms 75156 KB Output is correct
12 Correct 113 ms 73320 KB Output is correct
13 Correct 94 ms 77672 KB Output is correct
14 Correct 65 ms 71240 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 70364 KB Output is correct
2 Correct 122 ms 73408 KB Output is correct
3 Correct 94 ms 76524 KB Output is correct
4 Correct 76 ms 73260 KB Output is correct
5 Correct 75 ms 73168 KB Output is correct
6 Correct 91 ms 73304 KB Output is correct
7 Correct 72 ms 71632 KB Output is correct
8 Correct 91 ms 76464 KB Output is correct
9 Correct 127 ms 75416 KB Output is correct
10 Correct 143 ms 75596 KB Output is correct
11 Correct 111 ms 75348 KB Output is correct
12 Correct 112 ms 73588 KB Output is correct
13 Correct 124 ms 79408 KB Output is correct
14 Correct 91 ms 71452 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 75724 KB Output is correct
2 Correct 114 ms 73436 KB Output is correct
3 Correct 90 ms 79300 KB Output is correct
4 Correct 117 ms 75652 KB Output is correct
5 Correct 112 ms 75472 KB Output is correct
6 Correct 105 ms 75464 KB Output is correct
7 Correct 114 ms 73420 KB Output is correct
8 Correct 100 ms 79308 KB Output is correct
9 Correct 65 ms 71116 KB Output is correct