oj.uz

Submission #203205

# Submission time Handle Problem Language Result Execution time Memory
203205 2020-02-19T19:56:27 Z mdn2002 Ball Machine (BOI13_ballmachine) C++14
97.1429 / 100
 1000 ms 37328 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()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        int x;
        cin>>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;
        cin>>t>>x;
        if(t==1)
        {
            int to;
            while(x--)
            {
                pair<int,int>z=*--s.end();
                s.erase(--s.end());
                to=z.second;
                on[to]++;
            }
            cout<<to<<endl;
        }
        else
        {
            int l=0,r=n,mid;
            while(l<r)
            {
                mid=(l+r)/2;
                if(ck(x,mid))l=mid+1;
                else r=mid;
            }
            cout<<l-1<<endl;
            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:81:19: warning: 'to' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout<<to<<endl;
                   ^~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2680 KB Output is correct
2 Correct 502 ms 16236 KB Output is correct
3 Correct 374 ms 15992 KB Output is correct
4 Correct 6 ms 2680 KB Output is correct
5 Correct 7 ms 2808 KB Output is correct
6 Correct 8 ms 2936 KB Output is correct
7 Correct 10 ms 2936 KB Output is correct
8 Correct 12 ms 2936 KB Output is correct
9 Correct 35 ms 3576 KB Output is correct
10 Correct 94 ms 6136 KB Output is correct
11 Correct 504 ms 16376 KB Output is correct
12 Correct 369 ms 15964 KB Output is correct
13 Correct 440 ms 16248 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 9208 KB Output is correct
2 Correct 716 ms 29816 KB Output is correct
3 Correct 413 ms 22244 KB Output is correct
4 Correct 363 ms 11256 KB Output is correct
5 Correct 431 ms 11256 KB Output is correct
6 Correct 393 ms 11256 KB Output is correct
7 Correct 364 ms 9592 KB Output is correct
8 Correct 278 ms 9208 KB Output is correct
9 Correct 637 ms 30432 KB Output is correct
10 Correct 703 ms 29560 KB Output is correct
11 Correct 605 ms 29564 KB Output is correct
12 Correct 712 ms 26104 KB Output is correct
13 Correct 478 ms 32888 KB Output is correct
14 Correct 387 ms 22248 KB Output is correct

Subtask #3
37.1428571429 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 16376 KB Output is correct
2 Correct 915 ms 26828 KB Output is correct
3 Correct 633 ms 30328 KB Output is correct
4 Correct 504 ms 24592 KB Output is correct
5 Correct 572 ms 24312 KB Output is correct
6 Correct 567 ms 24420 KB Output is correct
7 Correct 546 ms 21752 KB Output is correct
8 Correct 636 ms 30324 KB Output is correct
9 Correct 819 ms 30168 KB Output is correct
10 Correct 938 ms 29944 KB Output is correct
11 Correct 952 ms 29944 KB Output is correct
12 Correct 899 ms 26616 KB Output is correct
13 Execution timed out 1094 ms 37328 KB Time limit exceeded
14 Correct 542 ms 22760 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 30292 KB Output is correct
2 Correct 847 ms 26788 KB Output is correct
3 Correct 500 ms 36856 KB Output is correct
4 Correct 898 ms 30304 KB Output is correct
5 Correct 848 ms 30200 KB Output is correct
6 Correct 645 ms 29816 KB Output is correct
7 Correct 883 ms 26616 KB Output is correct
8 Correct 509 ms 36728 KB Output is correct
9 Correct 412 ms 22248 KB Output is correct