oj.uz

Submission #42661

# Submission time Handle Problem Language Result Execution time Memory
42661 2018-03-01T23:53:04 Z XmtosX Ball Machine (BOI13_ballmachine) C++14
20.9524 / 100
 1000 ms 25516 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 (!cnt[i])
        {
            s.insert({pro[i],i});
        }
    }
    while (q--)
    {
        int t,k;
        cin >>t>>k;
        if (t==1)
        {
            int x;
            while (k--)
            {
                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=20;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 (k!=root)
            {
                if (!cnt[sprs[k][0]])
                    s.erase({pro[sprs[k][0]],sprs[k][0]});
                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 Execution timed out 1069 ms 2680 KB Time limit exceeded
2 Execution timed out 1072 ms 15072 KB Time limit exceeded
3 Incorrect 269 ms 15136 KB Output isn't correct
4 Execution timed out 1077 ms 15136 KB Time limit exceeded
5 Execution timed out 1079 ms 15136 KB Time limit exceeded
6 Incorrect 5 ms 15136 KB Output isn't correct
7 Execution timed out 1066 ms 15136 KB Time limit exceeded
8 Execution timed out 1068 ms 15136 KB Time limit exceeded
9 Execution timed out 1064 ms 15136 KB Time limit exceeded
10 Execution timed out 1068 ms 15136 KB Time limit exceeded
11 Execution timed out 1088 ms 15136 KB Time limit exceeded
12 Incorrect 297 ms 15136 KB Output isn't correct
13 Incorrect 330 ms 15136 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 15136 KB Output is correct
2 Execution timed out 1076 ms 23580 KB Time limit exceeded
3 Correct 291 ms 23580 KB Output is correct
4 Execution timed out 1080 ms 23580 KB Time limit exceeded
5 Execution timed out 1087 ms 23580 KB Time limit exceeded
6 Execution timed out 1078 ms 23580 KB Time limit exceeded
7 Execution timed out 1079 ms 23580 KB Time limit exceeded
8 Correct 183 ms 23580 KB Output is correct
9 Execution timed out 1067 ms 24084 KB Time limit exceeded
10 Execution timed out 1077 ms 24084 KB Time limit exceeded
11 Incorrect 443 ms 24084 KB Output isn't correct
12 Incorrect 438 ms 24084 KB Output isn't correct
13 Correct 314 ms 24084 KB Output is correct
14 Correct 300 ms 24084 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 205 ms 24084 KB Output isn't correct
2 Incorrect 455 ms 24084 KB Output isn't correct
3 Correct 284 ms 24084 KB Output is correct
4 Incorrect 288 ms 24084 KB Output isn't correct
5 Incorrect 293 ms 24084 KB Output isn't correct
6 Incorrect 297 ms 24084 KB Output isn't correct
7 Incorrect 311 ms 24084 KB Output isn't correct
8 Correct 298 ms 24084 KB Output is correct
9 Incorrect 469 ms 24084 KB Output isn't correct
10 Incorrect 489 ms 24140 KB Output isn't correct
11 Incorrect 486 ms 24140 KB Output isn't correct
12 Incorrect 473 ms 24140 KB Output isn't correct
13 Correct 487 ms 25516 KB Output is correct
14 Incorrect 431 ms 25516 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 25516 KB Time limit exceeded
2 Incorrect 432 ms 25516 KB Output isn't correct
3 Correct 352 ms 25516 KB Output is correct
4 Execution timed out 1055 ms 25516 KB Time limit exceeded
5 Execution timed out 1073 ms 25516 KB Time limit exceeded
6 Incorrect 447 ms 25516 KB Output isn't correct
7 Incorrect 446 ms 25516 KB Output isn't correct
8 Correct 353 ms 25516 KB Output is correct
9 Correct 344 ms 25516 KB Output is correct