oj.uz

Submission #63353

# Submission time Handle Problem Language Result Execution time Memory
63353 2018-08-01T14:37:55 Z Bodo171 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 838 ms 68356 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int nmax=100005;
vector<int> v[nmax];
int mn[nmax],r[nmax],wh[nmax],aib[nmax],negru[nmax],lev[nmax];
int tt[17][nmax];
int nr,n,q,i,j,x,R,type,poz,orig;
bool comp(int unu,int doi)
{
    return (mn[unu]<mn[doi]);
}
void dfs1(int x)
{
    for(int i=0;i<v[x].size();i++)
        {
            lev[v[x][i]]=lev[x]+1;
            dfs1(v[x][i]);
        }
    sort(v[x].begin(),v[x].end(),comp);
    mn[x]=x;
    if(v[x].size()) mn[x]=min(mn[x],mn[v[x][0]]);
}
void dfs2(int x)
{
    for(int i=0;i<v[x].size();i++)
        dfs2(v[x][i]);
    r[++nr]=x;wh[x]=nr;
}
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,int val)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
        aib[idx]+=val;
}
int get_poz()
{
    int ret=0;
    for(int p=16;p>=0;p--)
        if(ret+(1<<p)<=n&&aib[ret+(1<<p)]==(1<<p))
           ret+=(1<<p);
    ret++;
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>q;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        tt[0][i]=x;
        if(x)v[x].push_back(i);
        else R=i;
    }
    for(i=1;i<=16;i++)
        for(j=1;j<=n;j++)
          tt[i][j]=tt[i-1][tt[i-1][j]];
    dfs1(R);
    dfs2(R);
    for(i=1;i<=q;i++)
    {
        cin>>type>>x;
        if(type==1)
        {
            for(j=1;j<=x;j++)
            {
                poz=get_poz();
                update(poz,1);
                negru[r[poz]]=1;
            }
            cout<<r[poz]<<'\n';
        }
        else
        {
            orig=x;
            for(int p=16;p>=0;p--)
                if(negru[tt[p][x]])
                   x=tt[p][x];
            update(wh[x],-1);
            negru[x]=0;
            cout<<lev[orig]-lev[x]<<'\n';
        }
    }
    return 0;
}

Compilation message

ballmachine.cpp: In function 'void dfs1(int)':
ballmachine.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs2(int)':
ballmachine.cpp:28:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2808 KB Output is correct
2 Correct 621 ms 11272 KB Output is correct
3 Correct 349 ms 12008 KB Output is correct
4 Correct 7 ms 12008 KB Output is correct
5 Correct 6 ms 12008 KB Output is correct
6 Correct 8 ms 12008 KB Output is correct
7 Correct 9 ms 12008 KB Output is correct
8 Correct 12 ms 12008 KB Output is correct
9 Correct 46 ms 12008 KB Output is correct
10 Correct 102 ms 12008 KB Output is correct
11 Correct 585 ms 13956 KB Output is correct
12 Correct 355 ms 14604 KB Output is correct
13 Correct 676 ms 15952 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 15952 KB Output is correct
2 Correct 736 ms 25596 KB Output is correct
3 Correct 373 ms 25596 KB Output is correct
4 Correct 499 ms 25596 KB Output is correct
5 Correct 418 ms 25596 KB Output is correct
6 Correct 475 ms 25596 KB Output is correct
7 Correct 446 ms 25596 KB Output is correct
8 Correct 204 ms 25596 KB Output is correct
9 Correct 766 ms 32088 KB Output is correct
10 Correct 814 ms 32920 KB Output is correct
11 Correct 739 ms 34028 KB Output is correct
12 Correct 619 ms 34028 KB Output is correct
13 Correct 378 ms 39112 KB Output is correct
14 Correct 323 ms 39112 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 39112 KB Output is correct
2 Correct 661 ms 39112 KB Output is correct
3 Correct 401 ms 41916 KB Output is correct
4 Correct 433 ms 41916 KB Output is correct
5 Correct 551 ms 41916 KB Output is correct
6 Correct 517 ms 41916 KB Output is correct
7 Correct 511 ms 41916 KB Output is correct
8 Correct 459 ms 46648 KB Output is correct
9 Correct 671 ms 47236 KB Output is correct
10 Correct 816 ms 48200 KB Output is correct
11 Correct 838 ms 49804 KB Output is correct
12 Correct 805 ms 49804 KB Output is correct
13 Correct 806 ms 57508 KB Output is correct
14 Correct 641 ms 57508 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 57508 KB Output is correct
2 Correct 791 ms 57508 KB Output is correct
3 Correct 374 ms 61876 KB Output is correct
4 Correct 725 ms 61876 KB Output is correct
5 Correct 824 ms 61876 KB Output is correct
6 Correct 699 ms 61876 KB Output is correct
7 Correct 715 ms 61876 KB Output is correct
8 Correct 378 ms 68356 KB Output is correct
9 Correct 354 ms 68356 KB Output is correct