oj.uz

Submission #203208

# Submission time Handle Problem Language Result Execution time Memory
203208 2020-02-19T19:59:58 Z mdn2002 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 813 ms 37368 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,rt,st[100500],fn[100500],tim=1,mn[100500],on[100500],spt[100500][30],dp[100500];
vector<int>gr[100500];
set<pair<int,int> >s;
void dfs(int x)
{
    mn[x]=x;
    for(int i=0; i<gr[x].size(); i++)
    {
        int u=gr[x][i];
        dfs(u);
        mn[x]=min(mn[x],mn[u]);
    }
}
void dfs1(int x,int p)
{
    spt[x][0]=p;
    dp[x]=dp[p]+1;
    st[x]=tim++;
    vector<pair<int,int> >v;
    for(int i=0; i<gr[x].size(); i++)
    {
        int u=gr[x][i];
        v.push_back({mn[u],u});
    }
    sort(v.begin(),v.end());
    for(int i=gr[x].size()-1; i>=0; i--)
    {
        int u=v[i].second;
        dfs1(u,x);
    }
    fn[x]=tim;
}
bool ck(int x,int mid)
{
    int dif=mid;
    if(dif>dp[x])return 0;
    for(int i=0; i<=21; i++)
    {
        if((dif&(1<<i)))x=spt[x][i];
    }
    if(on[x]==0)return 0;
    else return 1;
}
int main()
{
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i=1; i<=n; i++)
    {
        int x;
        scanf("%d",&x);
        if(x==0)
        {
            rt=i;
            continue;
        }
        gr[x].push_back(i);
    }
    dfs(rt);
    dfs1(rt,0);
    for(int i=1; i<=n; i++)s.insert({st[i],i});
    for(int i=1; i<=25; i++)
    {
        for(int j=1; j<=n; j++)spt[j][i]=spt[spt[j][i-1]][i-1];
    }
    while(m--)
    {
        int t,x;
        scanf("%d",&t);
        scanf("%d",&x);
        if(t==1)
        {
            int to;
            while(x--)
            {
                pair<int,int>z=*--s.end();
                s.erase(--s.end());
                to=z.second;
                on[to]++;
            }
            printf("%d\n",to);
        }
        else
        {
            int l=0,r=n,mid;
            while(l<r)
            {
                mid=(l+r)/2;
                if(ck(x,mid))l=mid+1;
                else r=mid;
            }
            printf("%d\n",l-1);
            int dif=l-1;
            for(int i=0; i<=21; i++)
            {
                if((dif&(1<<i)))x=spt[x][i];
            }
            on[x]=0;
            s.insert({st[x],x});
        }
    }
}

Compilation message

ballmachine.cpp: In function 'void dfs(int)':
ballmachine.cpp:9:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gr[x].size(); i++)
                  ~^~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs1(int, int)':
ballmachine.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gr[x].size(); i++)
                  ~^~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
ballmachine.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&m);
     ~~~~~^~~~~~~~~
ballmachine.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~
ballmachine.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&t);
         ~~~~~^~~~~~~~~
ballmachine.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2808 KB Output is correct
2 Correct 234 ms 15992 KB Output is correct
3 Correct 131 ms 15992 KB Output is correct
4 Correct 6 ms 2680 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 7 ms 2936 KB Output is correct
7 Correct 8 ms 2936 KB Output is correct
8 Correct 9 ms 2936 KB Output is correct
9 Correct 18 ms 3576 KB Output is correct
10 Correct 39 ms 6008 KB Output is correct
11 Correct 253 ms 16120 KB Output is correct
12 Correct 128 ms 15992 KB Output is correct
13 Correct 185 ms 15968 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 9212 KB Output is correct
2 Correct 425 ms 29560 KB Output is correct
3 Correct 158 ms 22244 KB Output is correct
4 Correct 153 ms 11000 KB Output is correct
5 Correct 185 ms 10872 KB Output is correct
6 Correct 171 ms 10908 KB Output is correct
7 Correct 178 ms 9336 KB Output is correct
8 Correct 83 ms 9208 KB Output is correct
9 Correct 395 ms 29944 KB Output is correct
10 Correct 418 ms 29560 KB Output is correct
11 Correct 333 ms 29560 KB Output is correct
12 Correct 447 ms 26060 KB Output is correct
13 Correct 233 ms 32760 KB Output is correct
14 Correct 164 ms 22244 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 16532 KB Output is correct
2 Correct 592 ms 26876 KB Output is correct
3 Correct 464 ms 30244 KB Output is correct
4 Correct 362 ms 24748 KB Output is correct
5 Correct 395 ms 24492 KB Output is correct
6 Correct 387 ms 24312 KB Output is correct
7 Correct 381 ms 21776 KB Output is correct
8 Correct 459 ms 30456 KB Output is correct
9 Correct 533 ms 30468 KB Output is correct
10 Correct 701 ms 29776 KB Output is correct
11 Correct 623 ms 29820 KB Output is correct
12 Correct 602 ms 26872 KB Output is correct
13 Correct 813 ms 37368 KB Output is correct
14 Correct 255 ms 22628 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 30316 KB Output is correct
2 Correct 549 ms 26616 KB Output is correct
3 Correct 248 ms 36728 KB Output is correct
4 Correct 569 ms 30452 KB Output is correct
5 Correct 583 ms 29816 KB Output is correct
6 Correct 363 ms 29816 KB Output is correct
7 Correct 552 ms 26808 KB Output is correct
8 Correct 245 ms 36728 KB Output is correct
9 Correct 161 ms 22248 KB Output is correct