oj.uz

Submission #520955

# Submission time Handle Problem Language Result Execution time Memory
520955 2022-01-31T14:33:10 Z sicho_mohit Ball Machine (BOI13_ballmachine) C++14
100 / 100
 503 ms 29656 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std ;
const int N=1e5;
const int M=16;
vector<int>v[N+5];
int dis[N+5], parent[N+5][M+5];
int order[N+5], submin[N+5];
bool is[N+5];
int cnt=0;
bool comp(int a , int b)
{
    return submin[a]<submin[b];
}
void dfs1(int c , int p , int d)
{
    submin[c]=c;
    parent[c][0]=p;
    dis[c]=d;
    for (int i=1;i<=M;i++)
    {
        parent[c][i]=parent[parent[c][i-1]][i-1];
    }
    for (int i=0;i<v[c].size();i++)
    {
        if(v[c][i]!=p)
        {
        dfs1(v[c][i],c,d+1);
        submin[c]=min(submin[c],submin[v[c][i]]);
        }
    }
}
void arrange(int c , int p)
{
    for (int i=0;i<v[c].size();i++)
    {
        if(v[c][i]!=p)
        {
            arrange(v[c][i],c);
        }
    }
    order[c]=cnt++;
}
int findk(int node)
{
    for (int i=M;i>=0;i--)
    {
        if(is[parent[node][i]])
        {
            node=parent[node][i];
        }
    }
    return node;
}
int main ()
{
    int n  , q ;
    cin >> n >> q ;
    int root=1;
    for (int i=1;i<=n;i++)
    {
        int a;
        cin >> a ;
        if(a)
        {
        v[a].pb(i);
        v[i].pb(a);
        }
        else
        root=i;
    }
    dfs1(root,root,1);
    for (int i=1;i<=n;i++)
    sort(v[i].begin(),v[i].end(),comp);
    arrange(root,root);
    set<pair<int,int>>s;
    for (int i=1;i<=n;i++)
    {
        s.insert({order[i],i});
    }
    while(q--)
    {
        int t , k ;
        cin >> t >> k ;
        if(t==1)
        {
            if(k)
            {
            int ans=0;
            while(k--)
            {
                pair<int,int>temp=*(s.begin());
                s.erase(temp);
                is[temp.ss]=true;
                ans=temp.ss;
            }
            cout<<ans<<"\n";
            }
        }
        else
        {
            // find the highest ancestor from k
            int node=findk(k);
            cout<<dis[k]-dis[node]<<"\n";
            is[node]=false;
            s.insert({order[node],node});
        }
    }

}

Compilation message

ballmachine.cpp: In function 'void dfs1(int, int, int)':
ballmachine.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i=0;i<v[c].size();i++)
      |                  ~^~~~~~~~~~~~
ballmachine.cpp: In function 'void arrange(int, int)':
ballmachine.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i=0;i<v[c].size();i++)
      |                  ~^~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2636 KB Output is correct
2 Correct 301 ms 15452 KB Output is correct
3 Correct 242 ms 15172 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 5 ms 2776 KB Output is correct
8 Correct 5 ms 2764 KB Output is correct
9 Correct 19 ms 3424 KB Output is correct
10 Correct 55 ms 5732 KB Output is correct
11 Correct 346 ms 15320 KB Output is correct
12 Correct 257 ms 15196 KB Output is correct
13 Correct 280 ms 15264 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 8016 KB Output is correct
2 Correct 362 ms 25572 KB Output is correct
3 Correct 250 ms 21184 KB Output is correct
4 Correct 198 ms 9924 KB Output is correct
5 Correct 229 ms 9856 KB Output is correct
6 Correct 183 ms 9908 KB Output is correct
7 Correct 200 ms 8844 KB Output is correct
8 Correct 164 ms 8116 KB Output is correct
9 Correct 336 ms 25392 KB Output is correct
10 Correct 388 ms 25508 KB Output is correct
11 Correct 332 ms 25392 KB Output is correct
12 Correct 408 ms 23064 KB Output is correct
13 Correct 306 ms 26152 KB Output is correct
14 Correct 271 ms 21224 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 14020 KB Output is correct
2 Correct 448 ms 23500 KB Output is correct
3 Correct 262 ms 24000 KB Output is correct
4 Correct 280 ms 20776 KB Output is correct
5 Correct 267 ms 20768 KB Output is correct
6 Correct 275 ms 20768 KB Output is correct
7 Correct 267 ms 19108 KB Output is correct
8 Correct 280 ms 23964 KB Output is correct
9 Correct 503 ms 25556 KB Output is correct
10 Correct 378 ms 25548 KB Output is correct
11 Correct 385 ms 25608 KB Output is correct
12 Correct 370 ms 23608 KB Output is correct
13 Correct 408 ms 29656 KB Output is correct
14 Correct 308 ms 21652 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 25716 KB Output is correct
2 Correct 398 ms 23584 KB Output is correct
3 Correct 308 ms 29124 KB Output is correct
4 Correct 372 ms 25668 KB Output is correct
5 Correct 410 ms 25624 KB Output is correct
6 Correct 349 ms 25432 KB Output is correct
7 Correct 386 ms 23608 KB Output is correct
8 Correct 294 ms 29144 KB Output is correct
9 Correct 253 ms 21228 KB Output is correct