oj.uz

Submission #42658

# Submission time Handle Problem Language Result Execution time Memory
42658 2018-03-01T23:33:52 Z XmtosX Ball Machine (BOI13_ballmachine) C++14
8.57143 / 100
 452 ms 25644 KB 
#include <bits/stdc++.h>
using namespace std;
int n,minn[100005],root,q,sprs[100005][30],cnt[100005],pro[100005],cur;
vector <int> v[100005];
set <pair<int,int > > s;
bool yes[100005];
void dfs (int x,int p)
{
    minn[x]=x;
    if (p!=-1)
        sprs[x][0]=p;
    for (int i=1;i<30;i++)
        sprs[x][i]=sprs[sprs[x][i-1]][i-1];
    for (int i=0;i<v[x].size();i++)
    {
        if (v[x][i]!=p)
        {
            dfs(v[x][i],x);
            minn[x]=min(minn[x],minn[v[x][i]]);
            cnt[x]++;
        }
    }
}
void build (int x,int p)
{
    set <pair<int,int> > s1;
    for (int i=0;i<v[x].size();i++)
    {
        if (v[x][i]!=p)
        {
            s1.insert({minn[v[x][i]],v[x][i]});
        }
    }
    while (!s1.empty())
    {
        build(s1.begin()->second,x);
        s1.erase(s1.begin());
    }
    pro[x]=++cur;
}
int main()
{
    cin >>n>>q;
    for (int i=1;i<=n;i++)
    {
        int a;
        cin >>a;
        if (!a)
            root=i;
        else
        {
            v[a].push_back(i);
            v[i].push_back(a);
        }
    }
    dfs (root,-1);
    for (int i=1;i<=n;i++)
    {
        if (v[i].size()==1&&i!=root)
        {
            s.insert({pro[i],i});
        }
    }
    while (q--)
    {
        int t,k;
        cin >>t>>k;
        if (t==1)
        {
            int x;
            while (k--&&!s.empty())
            {
                x= s.begin()->second;
                s.erase(s.begin());
                yes[x]=true;
                if (x!=root)
                {
                    cnt[sprs[x][0]]--;
                    if (!cnt[sprs[x][0]])
                        s.insert({pro[sprs[x][0]],sprs[x][0]});
                }
            }
            cout <<x<<"\n";
        }
        else
        {
            int ans=0;
            for (int i=29;i>=0;i--)
            {
                if (yes[sprs[k][i]])
                {
                    k=sprs[k][i];
                    ans+= (1<<i);
                }
            }
            cout <<ans<<"\n";
            yes[k]=false;
            s.insert({pro[k],k});
            if (sprs[k][0]!=root)
            {
                s.erase({pro[sprs[k][0]],k});
                cnt[sprs[k][0]]++;
            }
        }
    }
    return 0;
}

Compilation message

ballmachine.cpp: In function 'void dfs(int, int)':
ballmachine.cpp:14:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                   ^
ballmachine.cpp: In function 'void build(int, int)':
ballmachine.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                   ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:83:20: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout <<x<<"\n";
                    ^

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2684 KB Output isn't correct
2 Incorrect 318 ms 14952 KB Output isn't correct
3 Incorrect 287 ms 15068 KB Output isn't correct
4 Incorrect 3 ms 15068 KB Output isn't correct
5 Incorrect 4 ms 15068 KB Output isn't correct
6 Incorrect 7 ms 15068 KB Output isn't correct
7 Incorrect 6 ms 15068 KB Output isn't correct
8 Incorrect 7 ms 15068 KB Output isn't correct
9 Incorrect 23 ms 15068 KB Output isn't correct
10 Incorrect 62 ms 15068 KB Output isn't correct
11 Incorrect 326 ms 15068 KB Output isn't correct
12 Incorrect 284 ms 15244 KB Output isn't correct
13 Incorrect 314 ms 15244 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 178 ms 15244 KB Output isn't correct
2 Incorrect 393 ms 23984 KB Output isn't correct
3 Incorrect 321 ms 23984 KB Output isn't correct
4 Incorrect 212 ms 23984 KB Output isn't correct
5 Incorrect 226 ms 23984 KB Output isn't correct
6 Incorrect 206 ms 23984 KB Output isn't correct
7 Incorrect 203 ms 23984 KB Output isn't correct
8 Incorrect 173 ms 23984 KB Output isn't correct
9 Incorrect 357 ms 23984 KB Output isn't correct
10 Incorrect 452 ms 24136 KB Output isn't correct
11 Incorrect 376 ms 24136 KB Output isn't correct
12 Incorrect 404 ms 24136 KB Output isn't correct
13 Incorrect 343 ms 24136 KB Output isn't correct
14 Incorrect 318 ms 24136 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 210 ms 24136 KB Output isn't correct
2 Incorrect 429 ms 24136 KB Output isn't correct
3 Correct 310 ms 24136 KB Output is correct
4 Incorrect 288 ms 24136 KB Output isn't correct
5 Incorrect 277 ms 24136 KB Output isn't correct
6 Incorrect 285 ms 24136 KB Output isn't correct
7 Incorrect 294 ms 24136 KB Output isn't correct
8 Correct 319 ms 24136 KB Output is correct
9 Incorrect 407 ms 24136 KB Output isn't correct
10 Incorrect 444 ms 24136 KB Output isn't correct
11 Incorrect 428 ms 24188 KB Output isn't correct
12 Incorrect 413 ms 24188 KB Output isn't correct
13 Correct 451 ms 25644 KB Output is correct
14 Incorrect 431 ms 25644 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 387 ms 25644 KB Output isn't correct
2 Incorrect 387 ms 25644 KB Output isn't correct
3 Incorrect 380 ms 25644 KB Output isn't correct
4 Incorrect 367 ms 25644 KB Output isn't correct
5 Incorrect 398 ms 25644 KB Output isn't correct
6 Incorrect 373 ms 25644 KB Output isn't correct
7 Incorrect 393 ms 25644 KB Output isn't correct
8 Incorrect 362 ms 25644 KB Output isn't correct
9 Incorrect 335 ms 25644 KB Output isn't correct